是时候东出了，刘邦出关慰问秦国的父老。三月，刘邦率军从临晋渡河，魏王豹领兵跟随。很快攻下河内，俘虏殷王司马卬，置河内郡。又南渡平阴津到雒阳，再降河南王申阳。这时有新城三老董公等挡在刘邦马前诉说义帝的死亡经过。汉王听后，大哭一场，遂为义帝发丧，举哀三日。然后向各诸侯王发布项羽大逆无道的罪状，并以此为借口号召各诸侯王率兵与自己一起讨伐项羽为义帝报仇。
檄文传到各国，立即得到不满项羽的诸侯的响应。魏王豹复书请从，刘邦叫他发兵相助。刘邦使者至赵，赵相陈余，却要刘邦杀张耳，方肯听命。刘邦不忍杀张耳，从兵中寻一与张耳面貌相似的人杀了，割下首级特示陈余，陈余信以为真，才发兵从汉。另一些诸侯则抱观望态度，不愿为项羽出力。
刘邦增调在关中的周勃、樊哙、夏侯婴等部至洛阳集中。四月，刘邦乘项羽胶着于城阳之际，率五诸侯军约计五十六万人，向楚都彭城进攻，萧何镇守栎阳，并筹集军资，自渭水、黄河顺流而下，以补给前方。曹参、周勃、樊哙、灌婴及赵军等部为进攻彭城之北路的纵队，由朝歌经定陶、胡陵，出肖县、彭城。薛欧、王吸、王陵、为南路纵队由宛经叶县、阳夏，出彭城。刘邦亲率夏侯婴、卢绾、靳歙、司马欣、董翳和殷王司马卬、常山王张耳、河南王申阳、韩王信、魏王豹等诸侯军为中路纵队，由洛阳经雍丘、睢阳出彭城，张良为军师，陈平为参乘。大军进抵外黄，彭越率军三万来会，刘邦命他继续袭扰梁地，掩护汉军侧背
五月，刘邦乘项羽深陷于齐国，无力抽身的机会，率领诸侯联军五十六万一举攻占西楚都彭城，刘邦在楚宫住下，又收了项羽的美人和财宝，这些都是项羽从秦国搜刮来的。一时的胜利让刘邦失去理智，整日与诸侯喝酒庆祝。项羽闻之，急率轻骑兵三万回袭彭城，项羽军夜间抵肖，利用拂晓，由西向东反击汉军侧背，早晨开始进攻，与汉军展开大战，联军无备，一时被杀十万，溺水淹死十万，只到中午56万联军就土崩瓦解了，刘邦仅率数十骑逃脱，以汉为首的反楚联盟瞬时瓦解。
刘邦大败，项羽从后追击，汉兵在谷、泗水二水被歼十余万。刘邦继续南走，想利用彭城南吕梁山区以资抵抗，但因项羽的猛烈追击而不能立足，又杀毙几万。项羽军追击汉逃兵至灵壁以东的睢水上，再斩杀汉军10余万人。刘邦军逃入睢水，溺死者不计其数。项羽军将刘邦及其残部包围了三层，正待聚歼之际，忽然西北大风猛袭而来，飞沙走石，树木连根拔起，一时间天昏地暗，吹打得项羽军阵营混乱。
所谓没有永远的朋友，也没有永远的敌人，只有永远的利益，正在刘邦危难之际，刘叔赶到，以刘叔之能也不一定能在万军丛中救下刘邦，刘叔急急找到灵璧吴家，说吴芮立了那么大功项羽分封不过小小衡阳王，若刘邦得到天下后，衡阳王吴芮肯定会得到大大封赏，到时候让你们自成一国，也诀不会兔死狗烹，吴家老祖正愁吴广只做了假王就一命呜呼，吴芮只是一个小王，又和英布结了亲，与张良交好，这次彭城之战后，项羽必然迁怒于他，吴家在听到刘叔所言后喜上眉头，看刘叔身上亦无龙气，也不再追究刘叔之过，吴家老祖遂同意出手一次，也只一次。
刘邦趁着天昏地暗之机，仅带10余名骑兵突围而逃。其父、其妻被楚军俘获，汉军几乎全军覆灭。
七月，章邯终于兵败自杀，刘邦完全解除了后顾之忧；且在逃往荥阳前便派吴家人说服英布反楚，联络彭越扰楚后方，又派韩信攻打北方势力，韩信遂攻魏，破代，灭赵。