劉邦於秦二世元年（公元前209年）九月於沛縣舉兵起義，轉眼間已是十月。秦以十月為歲首，已是秦二世二年，當時天下的形勢是：周文所統率的十萬義軍在戲水被章邯所統率的秦軍打得大敗而退還，繼武臣自立為趙王以後，他派往燕地的韓廣在燕地自立為燕王，狄人田儋在齊地自立為齊王，寧陵君魏公子魏咎被陳王立為魏王，項梁及項籍起兵於吳後，渡江加入反秦行列。
陳王陳勝、趙王武臣、燕王韓廣、齊王田儋、魏王魏咎以及項梁與項籍，是秦二世二年年初反秦各路諸侯中的幾支主要力量，無不擁有一定的實力。而起兵於沛縣的沛公劉邦，此時人少力單，處於舉步維艱的境地。
劉邦退守豐邑後，當時章邯率秦軍東下，秦泗水郡（治所在相縣，今安徽淮北市西北）名叫平的郡監率兵圍攻豐邑。沛公領兵出戰，擊破秦軍，命同鄉雍齒守衛豐邑，自己領兵進攻薛（今山東滕縣南）。泗水郡郡守名壯，在薛縣戰敗，逃至戚縣（今山東滕縣）。沛公的左司馬曹無傷捉住壯，並將他殺死。沛公領兵回到亢父（今山東濟寧市南），到達方與，一路沒有與敵軍交戰。此時，陳王派魏入周襳東向攻城略地，周襳派人對雍齒說：“豐曾是魏國的大梁秦軍攻占後的遷都之地，今魏王已平定數十城，您如果以豐邑投降魏國，魏國封你為侯，令你守衛豐城；如不投降，將屠殺豐城。”雍齒本來不願歸屬劉邦，在周襳利誘威脅之下，便反而為魏國守衛豐城。
沛公得知雍齒反叛，帶兵圍攻豐，未能攻下。由於患病，劉邦便回到沛縣。雍齒以豐邑背叛沛公，在精神上給沛公的打擊很大，他十分怨恨雍齒及豐邑子弟在形勢不利情況下的背叛行為。當時，章邯所率領的秦軍氣勢正盛，陳王陳勝被叛徒莊賈殺害，起義軍一時群龍無首，寧陵君與淩縣（今江蘇泗陽縣西北）人秦嘉合謀立楚國的王族後裔秦嘉為“假王”，駐紮在留（今江蘇沛縣東南）。沛公前往歸附景駒，想要向景駒借兵攻打豐邑。但秦將章邯、偏將司馬尼所率領的秦軍由西向東追擊，平定楚地，在相縣（泗水郡治所）屠城之後，到達碭（今河南夏邑縣東南）。東陽寧君、沛公率軍西上，與司馬尼交戰於蕭（今安徽蕭縣西北）西，不利，退回留縣，收編人馬，率兵攻碭。圍攻3日，碭城被攻下，收編碭城人馬，得五六千人。又進攻下邑（今安徽碭山縣），將下邑攻克，然後回軍豐縣。這時，沛公聞聽項梁在薛縣，便帶領百餘名騎兵前往拜見，項梁撥給他步兵5000人，五大夫將10人。沛公帶兵回還，攻打豐邑。
沛公投奔項粱一月有餘，項羽已攻克囊城（今河南襄城縣西）而還。項梁聞知陳勝已死，立楚懷王的孫子熊心為楚王，都於盱台（今江蘇盱台縣東北），項梁號武信君。項梁攻派沛公、項羽攻打城陽（今山東鄄城縣東南），攻克後屠城，駐軍於濮陽（今河南濮陽縣西南）東，與秦軍交戰，大破秦軍。戰，大破泰軍。
秦軍重新振作，堅守濮陽並引水環城以自衛。楚軍離去而進攻定陶（今山東定陶縣西北），未能攻下。沛公與項羽向西攻占土地，到達雍丘（今河南圮縣）城下，與秦軍交戰，犬破秦葷，三川郡郡守、秦丞相長子李由被斬首。沛公與項羽回兵攻打外黃（今河南民權縣西北），未能攻下。
項梁因屢敗秦軍，麵有驕色，不聽從上將軍宋義的勸諫，在定陶被章邯所帶領的秦軍打得大敗，項梁戰死。正在進攻陳留（今河南開封縣東南陳留城）的沛公、項羽聞知項梁戰死，與陳勝的部將呂臣一道率兵回師東進。呂臣駐軍在彭城（今江蘇徐州市）東麵，項羽駐軍在彭城西麵，沛公駐軍於碭山-一帶。
項梁的軍隊被秦朝的將領章邯攻破之後，章邯認為楚地已經不足為慮，於是就渡過黃河上北麵準備鎮壓河北地區的各路起義軍。項梁在秦二世二年九月的時候戰死。因為項梁的兵敗戰死，楚懷王感到十分恐懼不安，於是把都城遷到了彭城，並把呂臣和項羽的軍隊進行了合並，都交由自己率領。把劉邦任命為碭郡長，封為武安侯，率領碭郡兵馬；把項羽封為長安侯，號為魯公；將呂臣任命為司徒，並將其父親呂青任命為令尹。