沛公跟從項梁一個多月，項羽已經攻下襄城（河南省許昌市襄城縣）回來了。項梁把各路将領全部召到薛縣。聽說陳王确實是死了，因而立楚國後代懷王的孫子熊心為楚王，建都盱台（ｘū ｙí，一種說法，在唐人司馬貞《史記索隐》和張守節《史記正義》中有所記載，至今沿襲無異議，今江蘇省盱眙縣東北約25裡的盱眙山麓。另一種說法，江蘇省社會科學院王健教授，他認為項羽不可能進行千裡奔襲，因此攻打的是距離下邳較近的相縣襄城，泗水郡治相縣，位于今安徽省淮北）。項梁号稱武信君。呆了幾個月，向北攻打亢父（位于山東省濟甯市任城區喻屯鎮城南張村），援救東阿（今山東省聊城市東阿縣），擊敗了秦軍。齊國軍隊回去了，隻剩下楚軍單獨追擊敗逃之敵。另外讓沛公、項羽去攻打鹹陽（陝西省），屠戮了城陽（今山東省青島市城陽區，膠東郡）。軍隊駐紮在濮陽縣（濮陽縣是東郡的治所，今河南省東北部）東邊和秦軍交戰，打敗了秦軍。

秦軍重新振作，守住濮陽，在城周圍引水堅守。楚守撤兵去攻打定陶（山東省西南部、菏澤市中部），沒有攻下。沛公和項羽向西奪取土地，到了雍丘城下（今河南杞縣），和秦軍交戰，大敗秦軍，斬殺李由。又返回攻打外黃（今河南省民權縣西北的内黃集甯車灣村），沒有攻下。

項梁兩次打敗秦軍，露出驕傲的神色。宋義進谏，項梁不聽。秦朝給章邯增派了軍隊，趁着黑夜襲擊項梁軍隊。為了防止喧嘩，讓士兵口裡都銜着一根橫木棍，結果在定陶打敗了項梁的軍隊，項梁戰死。這時，沛公和項羽正在攻打陳留（今河南省開封市祥符區陳留鎮，當時屬于砀郡），聽說項梁已死，就帶兵和呂将軍一起向東進軍。呂臣的軍隊駐紮在彭城（今江蘇省徐州市）的東面，項羽的軍隊駐紮在彭城的西面，沛公的軍隊駐紮在砀縣。

章邯打敗了項梁的軍隊之後，就以為楚地的軍隊不值得擔憂，于是渡過黃河，向北進攻趙國，大敗趙軍。正當這個時候，趙歇立為趙王，秦将王離在钜鹿城（為钜鹿郡的郡治，今河北省邢台市平鄉縣平鄉鎮）包圍了趙歇的軍隊，這就是所謂的河北軍。

秦二世三年（前207），楚懷王看到項梁軍已被打敗，害怕了，就把都城從盱台遷到彭城，把呂臣、項羽的軍隊合在一起由他親自率領。任命沛公為砀郡太守，封為武安侯，統率砀郡的部隊。封項羽為長安侯，号稱魯公。呂臣（西漢初年新陽侯，漢文帝六年去世，原本是陳勝的部下）擔任司徒，他的父親呂青擔任令尹。

趙國幾次請求援救，懷王就任命宋義為上将軍，項羽為次将，範曾為末将，向北進兵救趙。命令沛公向西攻取土地，進軍關中。和諸将相約，誰先進入函谷關平定關中，就讓誰在關中做王。

這時候，秦軍強大，常常乘着勝利的威勢追擊敗逃之敵，諸将中沒有人認為先入關是有利的事。隻有項羽恨秦軍打敗了項梁的軍隊，很激憤，願意和沛公一起西進入關。

懷王手下的老将們都說：“項羽這個人敏捷勇猛，卻又狡猾傷人。項羽曾經攻下襄城，那裡的軍民沒有一個活下來，都被他活埋了。凡是他經過的地方，沒有不被毀滅的。再說，多次進攻，先前陳王、項梁都被打敗了，不如改派忠厚老實的人，實行仁義，率軍西進，向秦地的父老兄弟講明道理。秦地父老兄弟因為他們的君主暴虐而受苦已經很久了，現在如果真的能有位忠厚老實的人前去，不欺壓百姓，才會使秦地降服。項羽隻是敏捷勇猛，不能派他去。現在隻有沛公一向忠厚老實，可以派他去。”

懷王最終沒有答應項羽，而派了沛公率領大軍向西去奪取土地，一路收集陳勝、項梁的散兵。沛公取道砀縣到達成陽（今山東省菏澤市牡丹區胡集村東），與杠裡（今山東省菏澤市牡丹區東，屬于東郡的成陽縣）的秦軍對壘相持，結果擊敗了秦軍的兩支部隊。楚軍又出兵攻擊王離，把王離打得大敗。

沛公率兵西進，在昌邑（今山東省巨野縣大謝集鎮前昌邑村）與彭越（西漢初年名将、異姓諸侯王。與韓信、英布在當時被評價為“同功一體”，後世常習慣稱此三人為“漢初三大名将”）相遇。于是和他一起攻打秦軍，戰事不利。撤兵到栗縣（河南省夏邑縣），正好遇到剛武侯（柴武，西漢開國功臣、将領），就把他的軍隊奪了過來，大約有四千人，并入了自己的軍隊。又與魏将皇欣（應該最後沒有歸劉邦）、魏申徒武蒲（也不出名）的軍隊合力攻打昌邑，沒有攻下。沛公繼續西進，經過高陽（河北省保定市東南部，隸屬于巨鹿郡）。

郦食其（ｙì ｊī，秦末楚漢時期儒生，又被稱作“郦生”、“狂生”，是個具有實才的辯士、謀臣。在六十多歲時投奔西征秦國的劉邦，熟識戰國時期合縱連橫的謀略，是中國曆史上傑出的外交家）負責看管城門，他說：“各路經過此地的多了，我看隻有沛公才是個德行高尚忠厚老實的人。”

于是前去求見，遊說沛公。沛公當時正叉開兩腿坐在床上（踞，一種坐姿，指的是臀着地，足前伸的坐姿。在古代，這種坐姿被認為是不禮貌的，因為它暴露了身體的一部分，尤其是在穿着裙裝的情況下，可能會露出内褲，這在古代是極為失禮的）讓兩個女子給他洗腳。