接纳陈平的同月，刘邦从平阴津南渡黄河来到洛阳，继续向东推进。
新城邑的三老董公对刘邦说：“我听说‘顺德者昌，逆德者亡’，‘兵出无名，难以成事’，所以古语才说，要确立贼者，方能取胜。项羽不讲道义，谋害义帝，就是天下共诛之贼。以仁义之举，便可不依赖武力。我们的三军将士应全部身着素服，并布告天下，我军将东伐项贼，天下就会仰慕大王的德行，这堪比夏禹、殷汤、周武王三位古代贤王。”
刘邦说：“好！我倒是第一次听说这个说法。”于是刘邦大张旗鼓的为义帝发丧，还半脱衣服，哭灵三天，做足了戏码。同时还布告诸侯：“当初天下共立义帝，诸侯以臣事之，如今项羽放逐并杀害义帝，大逆不道。我刘邦亲自为义帝发丧，全军将士皆着素服。关中兵马悉数出发，再聚拢河东、河南、河内三郡将士，渡水南下，愿跟随诸王共同伐楚，为义帝报仇！”
董公给了刘邦一个绝佳的建议。实际上刘邦哪会在意义帝的死活和仇恨，不过是借义帝被杀大做文章，为自己攻楚披上道义的外衣罢了。项羽若能保全义帝，那自己仍然是反秦复楚的领袖，他可以借这面旗帜讨伐任何反对自己的人，即使刘邦想要反楚，也要花点功夫捏造一些理由。如今他亲手杀了义帝，看似为自己除去了紧箍咒，实际上却将“正义之师”的名义拱手让人，自己反倒成了“乱臣贼子”。而刘邦在诸侯中率先为义帝发丧，使自己成为了一种精神意义上的领袖。
四月，齐国的局势仍然十分胶着。田荣死后，他的的弟弟田横纠集了数万人马，在城阳反击楚军。项羽这时候已经知道刘邦启程东伐了，但他计划先平定齐国，再回过头收拾汉军。
项羽这么做大概有两方面的原因，一方面，齐国地理位置优越，能够开山采矿，煮海为盐，自古就富庶而强大，还与自己的楚国接壤，齐地不稳则楚国也不稳，先后实际控制齐国的田荣、田横这父子俩又一直是反楚的，所以必须要先处理好齐国的问题；另一方面，在项羽看来，刘邦的实力目前尚不足为虑，西边的事儿可以先放一放。项羽的判断基本是准确的，从后面彭城一役的结果就能印证。
刘邦抓住这个时机，带领所收降的五诸侯（常山王张耳、河南王申阳、魏王魏豹、汉王郑昌、殷王司马卬）兵马共五十六万向东攻楚。大军走到外黄时，彭越率三万将士归附汉军，因其收复了魏国不少城池，刘邦便拜彭越为魏国相国，令他平定梁地。
彭越是盗贼出身，活跃于乱世，没什么立场，只是逐利而战。他之前就帮助刘邦打过昌邑，也帮助田荣统一了齐国，还击败过楚军。
汉军趁项羽在齐国作战，一路向东攻入楚国大本营彭城，尽收美女和财物，并大摆酒宴。这里印证了刘邦的“好酒及色”，他也再也无法按捺住攻入咸阳时就被抑制的欲望，在项羽的国都纵酒狂欢了起来。
彭城被攻克后，项羽再不能置之不理了，于是命手下将领继续攻打齐国，自己亲率三万精兵南下解围彭城。
遗憾的是，项羽的部下败给了田横。田横立田荣的儿子田广为新齐王，自己为相国，独断军政大小事宜。田荣当年立田巿为傀儡齐王，如今自己的儿子也迎来了同样的命运。所以，古往今来，决定权利走向的从来都不是虚伪的位置，而是真正的实力，如二者兼而有之，则万事皆可成矣。
项羽军队在清晨发动对刘邦的攻击，中午就大破汉军，展现了出色的军事实力。汉军被迫南逃，楚军追击汉军至彭城南的睢（suī）水河。楚军大杀四方，汉军溃败，连人带尸十几万人挤入睢水河，以致河道堵塞，十分狼狈。
随后，楚军将汉军紧紧包围，刘邦凶多吉少。但帝王毕竟有帝王的命数，千钧一发之际，战场上忽然刮起了西北大风，霎时间房倒树折，飞沙走石，白昼昏如黑夜。楚军阵脚大乱，刘邦才得以趁此机会与身边数十人骑马逃走。
刘邦逃至沛县，令人寻找一家老小，但他们早已逃亡不知所处了。巧的是，后来刘邦在逃跑途中遇到了儿子和女儿，也就是后来的汉惠帝和鲁元公主，就让他们上了自己的车。遇到楚军追击时，刘邦看到马已经累了跑不快，难以脱身，情急之下竟然将一双儿女推下车。车夫滕公夏侯婴冒着被刘邦杀了的风险，又把他们拽上车，两个孩子才得以逃脱。
夏侯婴早年与刘邦交好，还替他受过刑，现在又救下刘邦的儿女，日后又在征臧荼时带着刘邦成功突围，绝对是汉朝第一车夫。刘邦死后，夏侯婴以太仆之职侍奉过汉惠帝、吕后和汉文帝，直至死在任上。
刘太公和吕后就没那么幸运了，他们和审食其走小路逃亡，反而遇到了楚军，被项羽抓做了人质。诸侯看到汉军大败，也都四散逃走了。塞王司马欣、翟王董翳投降项羽，殷王司马卬战死。
当时，吕后的哥哥周吕侯将兵屯居在下邑，刘邦便向西来此投奔。然后稍微收整剩余兵马，回到砀县驻扎下来。
刘邦收复关中后，尽管趁着项羽收拾齐国之机一路向东攻破彭城，但随即又被回师的项羽带兵区区三万打的落花流水。这是刘项二人首次正面交锋，刘邦惨败，靠运气才得以逃脱，并且为了活命，竟然置自己亲生骨肉的生死于不顾，要不是夏侯婴，大汉的长子、长女可能就早早丧命于楚军的铁蹄之下了。刘邦确有天子的运气和果决，但要想取天下，还有很长的路要走。