漢王率領大軍東渡黃河之後，魏王魏豹率領部下向漢王投降。魏豹原本是魏國王族的後代，他的兄長曾經在陳勝、吳廣起義的時候，被陳勝封為魏王，後來因為與章邯交戰失敗自殺身亡。魏豹繼承了魏王的王位。項羽的分封諸侯的時候想要把魏國的土地也分封出去，將魏豹封為西魏王。對項羽這樣的決定，魏豹表示強烈的不滿，所以當劉邦東征路過此地的時候，他就背叛的項羽，率領部隊向劉邦投降。接著，東征軍又把河內郡供了下來，並俘虜了殷王司馬顤，在這裏開設了漢政權屬下的河內郡。
此時，項王屬下的都尉陳平因懼怕項王誅殺而投奔漢王劉邦。陳平後來繼蕭相國、曹相國之後，與王陵同為漢帝國的左、右丞相，這裏對他的身世簡介如下。
陳平是陽武戶牖鄉（今河南蘭考縣東北）人，少年時家貧，好讀書。長大後身材魁梧，儀表堂堂，但不肯從事產業。閭裏祭祀社神時，請陳平主持分配祭肉，他把祭肉分得很均勻。父老們稱讚他說：“太好了，陳家這小子分得真均勻！”陳平感歎地說：“唉，如果讓我陳平管理天下，我也一定能像分祭肉這樣公平。”
陳勝起義後，立魏咎為魏王。此前，陳平曾侍奉過魏咎，這時被魏咎任命為太仆。陳平向魏咎獻計，魏咎不聽，又有人誹謗他，陳平因此而逃離魏王。
項羽略地到達黃河邊上，陳平投奔項羽，並隨從項羽入關，被賜予卿一級的爵位。項羽東歸彭城稱王，漢王還定三秦而後東進，殷王反對楚國，項羽封陳平為武信君，率魏咎留在楚國的部下，擊敗投降漢王的殷王而回。項羽派項悍任命陳平為都尉，賜黃金20鎰。不久，漢王攻占殷地，項羽大怒，想要殺掉前次平定殷地的將領。陳平因害怕被殺而派人將官印送還項羽，單身抄小路逃走。渡過黃河時，船夫懷疑他身上藏有金玉寶器，不時地注視他，想把他殺死在江上。陳平機智地解開衣服，袒露上身，協助船夫撐船。船夫見陳平一無所有，便沒有向他動手。
陳平到達修武（今河南獲嘉縣）投降漢王，漢王召見他，賜予酒食。飯後，漢王對客人說：“飯已用過，到館舍休息去吧。”
“我為要事而來，所談的事不可挨過今日。”陳平說。
於是，漢王將陳平留下，同他交談，談後很喜歡陳平，因而向陳平問道：“您在楚擔任什麼官職？”
“擔任都尉。”
當日，漢王任命陳平為都尉，為漢王參乘，成了漢王的衛士長，又主管監督和協調各將領，眾將領為此而嘩然，說道：“大王當天得到一個楚國的逃亡士卒，不知他的本事高下，便讓他陪乘大王，反而使令他監督我們這些老將！”
漢王聞知有些老將對重用陳平不服，反而對陳平更加親近，帶他一同東進討伐項王。
漢王南下從平陰津（古渡口名，在今河南孟津東北）渡過黃河，到達洛陽。行軍途中，新城（今河南伊川縣西南）某鄉的一位姓董的“三老”，人稱董公，他在路旁攔住漢王的馬頭，向漢王訴說項王殺害義帝的經過，並說道：
“我聽說‘順德者昌，逆德者亡’；‘兵出無名，事故不成’，所以說：‘明其為賊，敵乃可服。如今項羽行為無道，放逐並殺害他的君主，是天下的亂臣賊。已有仁，則天下歸之，可不用勇而天下自然歸服；己有義，則天下奉之，可不用力而天下自定。大王應下令三軍將士為義帝身穿服，遍告天下諸侯，舉兵共同伐楚。如此，則四海之內沒有不仰望你的大德，這就是湯、文、武三王當年所奉行的取天下之道。’”
漢王認為董公講得很對，袒臂大哭，下令全軍為義帝發喪，為義帝舉哀3日，分派使者通告各路諸侯：
“天下共同擁立義帝，都甘願向他北麵稱臣。如今項羽放逐義帝，指使九江王黥布、衡山王吳芮，臨江王共敖把義帝殺死於江南，這是大逆不道。寡人親自為義帝發喪，諸侯也應身穿孝服。我將調動關中全部兵馬，征集河南、河東、河內三郡的士兵，沿長江、漢水南下，願隨同諸侯去江南討伐楚國殺害義帝的那些人。”
漢王派出的使者到達趙國，趙相陳餘對使者說：“漢殺死張耳，方能發兵隨從伐楚。”於是，漢王尋找一個相貌同張耳類似的人，斬首後將人頭送給陳餘，陳餘派兵助漢伐楚。