沛公病了，便回到沛縣。沛公怨恨雍齒和豐邑子弟都背叛他，聽說東陽寧君、秦嘉立景駒為假王，住在留縣，就去依附他們，想借兵攻打豐邑。這時，秦將章邯在追擊陳王的部隊，別將司馬率軍北向，攻占楚地，在相屠城，到了碭縣。東陽寧君、沛公引兵西進，與司馬在蕭縣西麵交戰，沒有占著便宜。退回來收集散兵，屯聚留縣，引兵攻碭，三天就攻下了碭邑。收編碭縣降兵，得到五六千人，進攻下邑，攻打了下來。沛公回軍豐邑。聽說項梁在薛縣，帶了隨從騎兵一百多人去見項梁。項梁給沛公增撥士兵五千人，五大夫一級的將領十人。沛公回來，引兵攻豐。
沛公跟隨項梁一個多月，項羽已經攻克襄城回來。項梁把各路將領都召集到薛縣，聽說陳王確實死了，就立楚國後人楚懷王的孫子心為楚王，建都盱台。項梁號為武信君。停了幾個月，項梁向北攻打亢父，救援東阿（被圍的齊軍），打敗了秦軍。齊軍回到齊，楚軍單獨追擊敗兵。派沛公、項羽另率軍隊攻打城陽，大肆殺戮城中軍民。沛公、項羽駐軍濮陽東麵，與秦軍接戰，擊破了秦軍。
秦軍又振作起來，固守濮陽，決水自環。楚軍離去，轉攻定陶，定陶沒有攻下。沛公和項羽向西攻城略地，到了雍丘城下，與秦軍交戰，大破秦軍，殺了李由。回軍攻打外黃，外黃沒有攻克。
項梁又一次打敗了秦軍，有驕傲的神色。宋義勸誡他，他不聽。秦派兵增援章邯，夜間銜枚偷襲項梁，在定陶大破項梁，項梁戰死。沛公和項羽正在攻打陳留，聽說項梁死了，帶兵和呂將軍一塊向東迸發。呂臣駐紮在彭城東麵，項羽駐紮在彭城西麵，沛公駐紮在碭。
章邯已經打垮了項梁的軍隊，以為楚地的敵人不用擔心了，就渡過黃河，北進攻打趙地，大破趙軍。這個時候，趙歇為趙王，秦將王離圍困趙歇在钜鹿城。被圍在钜鹿的軍隊，這就是所謂的“河北之軍”。
秦二世三年，楚懷王看到項梁的軍隊被打垮了，心裏恐懼，遷離盱台，建都彭城，合並呂臣、項羽的軍隊，親自統率。以沛公任碭郡長，封為武安侯，統領碭郡的軍隊。封項羽為長安侯，號為魯公，呂臣任司徒，他的父親呂青作令尹。
趙多次請求救援，楚懷王就以宋義為上將軍，項羽為次將，範增為末將，北上援救趙。命令沛公西出略地，打入關中。同將領們約定：先攻入關中的，就封在關中做王。
這時候，秦軍強盛，常常乘勝追擊，眾將領沒有認為先入關是有利的。惟獨項羽痛恨秦打垮了項梁的軍隊，心中憤激，願和沛公西進入關。懷王的老將都說：“項羽為人輕捷而凶猛，狡詐而殘忍。項羽曾經攻打襄城，襄城沒有留下一個活人，全都活埋了。所經過的地方，無不殘殺毀滅。況且楚軍多次進兵攻取，（沒有獲勝，）以前陳王、項梁都失敗了。不如另派寬厚長者，以正義為號召，向西進發，把道理向秦國父老兄弟講清楚。秦父老兄弟受苦於他們君主的統治很久了，現在如果真能有寬厚長者去關中，不加欺淩暴虐，應該能夠拿下關中。而今項羽剽悍，不可派遣。”終於沒有答應項羽，而派遣沛公西進攻取秦地。沛公收集陳王、項梁的散兵，路經碭，到達鹹陽，與杠裏的秦軍對壘，打敗了秦軍的兩支部隊。楚軍出兵攻擊王離，把他的軍隊打得片甲不留。
沛公引兵西進，在昌邑遇見彭越，就和他一起攻打秦軍，這一仗沒有打贏。回到栗縣，遇到剛武侯，奪了他的軍隊，大約四千多人，（與沛公原來的隊伍）合並在一起。沛公與魏將皇欣、魏申徒武蒲的軍隊聯合攻打昌邑，昌邑沒有攻下，西進路過高陽。酈食其為裏監門，說：“將領們路過這裏的很多，我看沛公是一個大人物，有仁厚長者的風度。”就去求見遊說沛公。沛公正坐在床上，伸著兩腿，讓兩個女子給他洗腳。酈生不下拜，深深地作了個揖，說：“足下一定要消滅殘暴無道的秦朝，就不應該伸著兩腿接見長者。”於是沛公站了起來，整理好衣服，向他道歉，請他到上座。酈食其勸沛公襲擊陳留，獲得陳留積聚的糧米。沛公就封酈食其為廣野君，酈商為將領，統率陳留的軍隊，和沛公一起攻打開封，開封沒有攻下。向西與秦將楊熊在白馬打了一仗，在曲遇的東麵又接著戰鬥，大破楊熊軍。楊熊逃往滎陽，秦二世派使斬首示眾。沛公向南攻打潁陽，屠了潁陽城。依靠張良攻占了韓國的轘轅。