汉王率领大军东渡黄河之后，魏王魏豹率领部下向汉王投降。魏豹原本是魏国王族的后代，他的兄长曾经在陈胜、吴广起义的时候，被陈胜封为魏王，后来因为与章邯交战失败自杀身亡。魏豹继承了魏王的王位。项羽的分封诸侯的时候想要把魏国的土地也分封出去，将魏豹封为西魏王。对项羽这样的决定，魏豹表示强烈的不满，所以当刘邦东征路过此地的时候，他就背叛的项羽，率领部队向刘邦投降。接着，东征军又把河内郡供了下来，并俘虏了殷王司马顤，在这里开设了汉政权属下的河内郡。
此时，项王属下的都尉陈平因惧怕项王诛杀而投奔汉王刘邦。陈平后来继萧相国、曹相国之后，与王陵同为汉帝国的左、右丞相，这里对他的身世简介如下。
陈平是阳武户牖乡（今河南兰考县东北）人，少年时家贫，好读书。长大后身材魁梧，仪表堂堂，但不肯从事产业。闾里祭祀社神时，请陈平主持分配祭肉，他把祭肉分得很均匀。父老们称赞他说：“太好了，陈家这小子分得真均匀！”陈平感叹地说：“唉，如果让我陈平管理天下，我也一定能像分祭肉这样公平。”
陈胜起义后，立魏咎为魏王。此前，陈平曾侍奉过魏咎，这时被魏咎任命为太仆。陈平向魏咎献计，魏咎不听，又有人诽谤他，陈平因此而逃离魏王。
项羽略地到达黄河边上，陈平投奔项羽，并随从项羽入关，被赐予卿一级的爵位。项羽东归彭城称王，汉王还定三秦而后东进，殷王反对楚国，项羽封陈平为武信君，率魏咎留在楚国的部下，击败投降汉王的殷王而回。项羽派项悍任命陈平为都尉，赐黄金20镒。不久，汉王攻占殷地，项羽大怒，想要杀掉前次平定殷地的将领。陈平因害怕被杀而派人将官印送还项羽，单身抄小路逃走。渡过黄河时，船夫怀疑他身上藏有金玉宝器，不时地注视他，想把他杀死在江上。陈平机智地解开衣服，袒露上身，协助船夫撑船。船夫见陈平一无所有，便没有向他动手。
陈平到达修武（今河南获嘉县）投降汉王，汉王召见他，赐予酒食。饭后，汉王对客人说：“饭已用过，到馆舍休息去吧。”
“我为要事而来，所谈的事不可挨过今日。”陈平说。
于是，汉王将陈平留下，同他交谈，谈后很喜欢陈平，因而向陈平问道：“您在楚担任什么官职？”
“担任都尉。”
当日，汉王任命陈平为都尉，为汉王参乘，成了汉王的卫士长，又主管监督和协调各将领，众将领为此而哗然，说道：“大王当天得到一个楚国的逃亡士卒，不知他的本事高下，便让他陪乘大王，反而使令他监督我们这些老将！”
汉王闻知有些老将对重用陈平不服，反而对陈平更加亲近，带他一同东进讨伐项王。
汉王南下从平阴津（古渡口名，在今河南孟津东北）渡过黄河，到达洛阳。行军途中，新城（今河南伊川县西南）某乡的一位姓董的“三老”，人称董公，他在路旁拦住汉王的马头，向汉王诉说项王杀害义帝的经过，并说道：
“我听说‘顺德者昌，逆德者亡’；‘兵出无名，事故不成’，所以说：‘明其为贼，敌乃可服。如今项羽行为无道，放逐并杀害他的君主，是天下的乱臣贼。已有仁，则天下归之，可不用勇而天下自然归服；己有义，则天下奉之，可不用力而天下自定。大王应下令三军将士为义帝身穿服，遍告天下诸侯，举兵共同伐楚。如此，则四海之内没有不仰望你的大德，这就是汤、文、武三王当年所奉行的取天下之道。’”
汉王认为董公讲得很对，袒臂大哭，下令全军为义帝发丧，为义帝举哀3日，分派使者通告各路诸侯：
“天下共同拥立义帝，都甘愿向他北面称臣。如今项羽放逐义帝，指使九江王黥布、衡山王吴芮，临江王共敖把义帝杀死于江南，这是大逆不道。寡人亲自为义帝发丧，诸侯也应身穿孝服。我将调动关中全部兵马，征集河南、河东、河内三郡的士兵，沿长江、汉水南下，愿随同诸侯去江南讨伐楚国杀害义帝的那些人。”
汉王派出的使者到达赵国，赵相陈余对使者说：“汉杀死张耳，方能发兵随从伐楚。”于是，汉王寻找一个相貌同张耳类似的人，斩首后将人头送给陈余，陈余派兵助汉伐楚。
此时，项王正在北击齐国，与田荣交战于城阳，田荣兵败，逃至平原（今山东平原县南），被平原百姓杀死。三齐全部向楚军投降。项羽乘胜焚烧齐地的城郭，虏走齐地的子女。齐人因楚军的暴行而叛楚，田荣的弟弟田横立田荣的儿子田广为齐王，齐王田广于城阳（今山东鄄城县境）起兵反楚。
项羽因田广起兵反楚，率兵攻城阳，未能攻下。此时，项羽已得知汉王率兵东进，然而既然已与齐兵交战，想要击溃齐兵之后再攻击汉军，而这时汉王已率领常山王张耳、河南王申阳、韩王郑昌、魏王魏豹、殷王司马顤等五路诸侯共56万大军，向楚都彭城进发。到达外黄（今河南民权县西北），彭越又率三万余士兵归属汉王。汉王对彭越说：“彭将军收复魏地十余座城池，想急于立魏国的后代为王。今西魏王魏豹，确实是魏国王室的后代。”于是任命彭越为魏王的相国，率领其部下的士兵攻占魏国的故地。
同年四月，在彭城空虚的情况下，汉王所统率的五路诸侯共60万大军攻入彭城。汉王从未统率过这么众多的军队，也从未取得过这么令他高兴的重大胜利。在彭城，汉王没收了项王的货宝、美人，与五路诸侯整日大摆宴会，饮酒作乐，沉浸在胜利后的狂喜之中。
项王闻知彭城危在旦夕，便命令部下诸将率兵继续攻击齐军，自己亲自率3万精兵南下。楚军从曲阜（今山东曲阜市）出发，经胡陵（今山东鱼台县东南）南下。此时，汉王已攻入彭城，正在城中“日置酒高会”。项王便从彭城西面的萧（今安徽萧县西北）发起攻击，早晨向东进击，攻至彭城城下。中午，大破汉军。汉军全线溃败，相继被挤入谷水、泅水之中，汉军被杀死者多达十余万人。汉军都是向南逃走，楚军追击至灵璧（今安徽淮北市西南）的睢水上。汉军退却，被楚军挤逼，伤亡惨重，又有十多万汉军被挤入睢水中，睢水因此而不能流动。
楚军将汉王重重包围，汉王已无法冲出重围。这时，西北方突然刮起狂风，飞沙走石，天昏地暗，迎面向楚军扑来，楚军顿时大乱，包围圈也随之溃散。汉王趁着狂风所赐给他的一线生机，带领十余名骑兵逃脱而走。汉王想路过沛县，带领家眷向西逃走，而楚军也派人到沛县捕拿汉王家眷。汉王家眷已经逃走，未能与汉王相见。
在逃亡途中，汉王遇见了女儿（后封鲁元公主）和儿子（后为孝惠帝），便同车载行。楚骑兵从后面追赶汉王，汉王急于逃脱，便把女儿和儿子推下车去，以便减轻车的载重而加速前行，但同行的滕公夏侯婴却下车把两个孩子抱到车上。汉王多次把儿子，女儿推下车去，滕公便多次下车收载，并向汉王说道：“情况虽然紧急，但马又不可跑得再快些，为什么把孩子抛弃不管？”就这样，汉王一行终于逃脱了楚军的追击。
汉王派人寻找父亲和妻子吕雉，但没有找到。审食其护送汉王的父亲和妻子抄小路逃走，反而遇到了楚军，成了楚军的俘虏。事情上报项王，项王便把他们安置在军营中，作为人质。
汉王的60万大军在项王的3万精兵面前一触即溃，溃不成军，死伤三十余万人，余者也都四面逃散。诸侯联军在兵力上以20比1的优势惨遭失败，其原因是60万大军是临时凑合的，而项王3万精兵却是跟随他作战多年，训练有素，战斗力极强。楚军统帅项羽又勇猛无比，独具超人的军事天才和胆略。如此的统帅率领着如此的精兵，与汉王统帅的诸侯联军交战，岂止是以一当十。再说，汉王与诸侯攻入彭城后，整日饮酒盛会，没有料到楚军会如此迅速地从天而降。汉军既无防备，又缺乏统一的指挥，怎能不惨败于楚军的猛攻之下。
汉王东征虽然取得了胜利，但这些战争都是在没有和项羽的部队产生正面冲突的情况下而产生的，因此这样的胜利对于刘邦来说是不能算作与楚军进行正面交战获得的真正胜利。但是刘邦在彭城的惨败，却是抹不掉的败局，在这场战争中，刘邦损失惨重，最后他只能带领十多名起兵突出重围，狼狈逃走。这些教训让刘邦明白，自己在与楚军交战上，还是处于劣势。