汉王还定三秦而东，殷王反楚。项羽乃以平为信武君，将魏王咎客在楚者以往，击降殷王而还……汉王攻下殷，项王怒，将诛定殷者将吏……平遂至修武降汉。
——《史记·陈丞相世家》
汉二年（前206）十月，在基本平定三秦后，刘邦决定趁着项羽主力被牵制在齐地的机会，东出争夺天下，而他首先要面对的，就是堵在函谷关外的河南王申阳。
而就在刘邦平定三秦之际，被陈馀击败的张耳来到关中投奔刘邦，对于故交好友的来投，刘邦十分高兴，以厚礼接待了他。在与老友的交谈中，刘邦这才得知，河南王申阳竟然曾是张耳的部下。
之后，刘邦留部分兵力平定三秦尚未归降地区，并继续围困章邯于废丘，自己则亲率大军出关至陕县，镇抚关外父老，并委托张耳前去招降申阳。迫于汉军压力，再加上旧主张耳的劝说，建都洛阳的河南王申阳最终选择了归降刘邦，刘邦废其封国为河南郡。
申阳归降后，刘邦又以韩信为韩国太尉，率兵南下攻取韩国旧地。
此韩信并非“汉初三杰”之一的那个韩信，而是战国时期韩国第八位国君韩襄王的庶孙，为了对两人加以区分，后世称之为韩王信。
当初刘邦西入咸阳时，在颍川替韩王韩成平定韩国旧地。作为韩国宗室子孙，韩王信在秦末时期也招募了一些军队，想要恢复韩国，但与张良一样，迟迟难以打开局面。得知刘邦替韩成恢复韩国后，韩王信于是率部投奔刘邦，被任命为韩国将军，率本部兵马跟随刘邦自入关。
刘邦被封为汉王后，韩王信跟随刘邦南下汉中郡，对于项羽将刘邦分封在巴蜀之地愤愤不平，对刘邦说，“项羽把自己的部下都封在中原附近地区，只把大王封到这偏远的地方，这是一种降职调迁！大王麾下的士兵都是崤山以东的人，他们都翘首以盼，急切盼望能够回到家乡，趁着他们锐气强盛向东进发，就可以争夺天下！”
刘邦还定三秦，张良自楚国返回，告知韩王韩成已被项羽所杀，刘邦便许诺韩信和张良，将来会封韩信为韩王，重立韩国。因此，在出关平定河南郡后，刘邦便以韩王信为韩国太尉，率兵南下收复韩国旧地。
彼时，郑昌刚刚被项羽封为韩王不久，再加上出身韩国宗室的韩王韩成被项羽所杀，韩地官民对郑昌多有不服，郑昌尚未来得及巩固统治、收拢人心，韩王信便率兵南下了，郑昌得知消息，连忙征调军队，亲自率军北上迎战。
韩王信率兵南下后，郑昌仓促征调的军队一触即溃，无奈只能困守阳城，韩王信攻城不下，便率兵转战周边各地，很快便平定了十几座城池。
刘邦在稳固了河南郡的统治后，率兵南下增援韩王信，双方合军一处，猛攻郑昌于阳城。郑昌自知坚守已经无济于事，遂献城投降，刘邦于是封韩信为韩王，故被称为韩王信。
平定韩地之后，刘邦率兵退回河南郡，整顿兵马准备北渡黄河攻打殷王司马卬，彻底打通东出通道。
当得知刘邦仅用月余时间，便接连降服了两位诸侯王后，仅拥有河内郡一郡之地的司马卬，自知无力抵御刘邦，为了避免遭到刘邦进攻，于同年十一月公开反楚，并派人向刘邦示好，请求归附。刘邦见其如此识相，便放弃了北上的计划，命司马卬继续镇守封地。
在申阳、郑昌投降，司马卬主动归附后，项羽将刘邦堵死在关中的计划彻底泡汤，刘邦就此打开了从关中到西楚的东进通道。
虽然东进通道已经打通，但由于关中地区仍有零星抵抗，再加上担心魏王魏豹在自己东进之后偷袭关中，刘邦并没有急着继续东进与项羽正面开战，而是暂时退回关中休整、稳定后方。
汉二年（前205年）十一月，鉴于关中已经基本平定，刘邦将都城由汉中南郑迁至关中的秦国旧都栎阳，命人修缮河上塞，并将秦朝原先的皇家动植物园地及水池，开放给百姓耕种。相较于当初征发百姓向咸阳运粮，却禁止百姓食用咸阳周围三百里以内粮食的胡亥，刘邦此举无疑大获人心。
汉二年（前205年）二月，刘邦又下令拆除了象征秦朝统治的社稷坛，建立汉朝的社稷坛。此后，刘邦又多次下达政令，普施恩德，赐民爵禄，以收复治下人心。
刘邦下令，鉴于巴蜀、汉中百姓此前供应军需负担极重，免其租税两年，而关中士卒凡是从军者，也全都免除其家赋税一年，此举不仅使刘邦大获百姓拥戴，同时也大肆激发了百姓的从军热情；刘邦又下令，凡普通百姓年逾五十，德高望重，能领导大家为善的，任命其为三老，每乡一人，又择乡三老一人为“县三老”，与县令、县丞、县尉共议县内事务，并免除其役戍，给予了百姓参议政事的权力；刘邦还下令，每年十月新年伊始，由朝廷赐予百姓酒肉，与民同乐。
就在刘邦退回关中，巩固自身统治之际，得知河南王申阳、韩王郑昌和殷王司马卬全部归降刘邦的项羽大为震惊，更让他担心的是，如今楚国主力皆在齐地，一旦刘邦向西楚用兵，不仅自己要陷入腹背受敌的危险境地，防御空虚的西楚国也势必难以抵挡刘邦的攻势。
项羽在与范增商议后认为，如今想要收复河南、颍川一带已经十分困难，而且就算成功收复，若无重兵驻守，也很难抵御刘邦的大军，与其如此，倒不如出兵攻打河内郡，只要迫使司马卬归附自己，一旦刘邦东进攻打楚国，司马卬便可南渡黄河进入洛阳盆地，切断刘邦的后勤补给。而且，有黄河作为阻隔，刘邦想要攻打河内郡，并不容易。
于是，为了阻止刘邦东进，项羽封陈平为武信君，命其统率魏王咎留在楚国的宾客，带兵攻打司马卬。
对于殷王司马卬来说，无论是面对汉王刘邦，还是面对西楚霸王项羽，他都没有足够的实力对抗，得知陈平率军来攻，而刘邦又退回了关中，司马卬果断又掉头倒向了项羽，表示自己当初反楚，乃是迫于刘邦压力不得已而为之。得知陈平取胜归来，项羽总算松了口气，派项悍拜陈平为都尉，并赐金二十镒。
汉二年（前205年）三月，在平定了废丘以外的三秦之地后，刘邦命萧何坐镇栎阳，负责关中的治理，并筹集物资补给军队，郦商、周勃等将镇守关中地区，在继续围困废丘章邯的同时，防备南阳的王陵和楚军入关，而他自己则率领主力自临晋东渡黄河，攻入了西魏王魏豹的封地。
魏豹对于项羽的分封实际上也多有不满。当初他的兄长魏王咎自尽后，魏豹便逃奔了楚国，后楚王熊心交给他几千军队，让魏豹收复魏国旧地，在项羽统率诸侯联军入关时，魏豹已经攻占了魏地二十余城。
项羽分封之时，却将魏豹迁徙到了河东地区，封为了西魏王，而位居中原、较为富庶的魏地则被项羽纳入了西楚。
魏豹本就对项羽没有让自己恢复魏国而颇为不满，再加上自身实力确实不如刘邦，因此在刘邦渡过黄河东进之后，魏豹果断倒戈归顺刘邦，并表示若是有朝一日东进攻楚，自己愿意率兵相随。
由于司马卬再度倒戈归楚，在魏豹归附之后，刘邦便又率兵南下攻打河内郡，这次刘邦没有给他归降的机会，直接率兵将其击败，并俘虏了司马卬。之后，刘邦废司马卬封地为河内郡。
项羽得知刘邦再度东出，魏豹和司马卬全部归附刘邦后，迁怒于曾率兵攻打司马卬的陈平等人，决定将他们全部处死。
陈平原为魏人，年少时家中贫困，可他却偏偏喜欢读书、郊游，而不事生产。陈平与兄长陈伯住在一起，为了使陈平有时间外出游学，陈伯不仅承担了家中的所有农活，还休掉了厌恶陈平的妻子。
后来，陈平靠着给乡邻料理丧事贴补家用，有个叫张负的富人在参加他人葬礼时，遇见了陈平，见陈平长相俊美，而且在当地颇有名望，认为他将来必成大事，便想将孙女嫁给他。张负的孙女先后嫁了五次，丈夫都去世了，以致没有人敢再娶她，而陈平却并不在意，两人成婚之后，在张负的资助下，陈平家资日渐宽裕，他郊游的范围也越来越广。
秦末天下大乱，魏咎被立为魏王后，陈平便辞别兄长前往投奔了魏王魏咎，但不久便因谗言而被迫离魏，又转投到项羽麾下做了谋士，并跟随项羽西入关中。
如今听说项羽要处死自己，不愿坐以待毙的陈平，便挂印封金，偷偷地溜走了。陈平离开楚地后，短暂犹豫过后，便决定前往投奔汉王刘邦，于是一路西行，天黑时来到了黄河边上。
陈平见河边停靠着一艘小船，便请船夫送自己过河，等船驶离岸边，却从船舱里又走出一个船夫，两人见陈平长的高大俊美又是独自一人，猜想他可能是逃亡的将士，便意图将其杀了谋夺财物。
陈平见两人面色不善，心知自己遇到了水盗。陈平自幼便鬼点子多，面对如此绝境，他很快便想到了应对之策。只见他将衣衫脱掉扔到船上，然后光着膀子跑去帮船夫划船，船夫见其腰间并无钱财，衣服掉在船上也没发出什么声音，不禁暗道一声晦气，只当遇到了穷鬼，这才打消了谋财害命的念头。
陈平渡过黄河后，打听到刘邦正驻军修武休整，便一路前往修武，后经汉将魏无知的推荐，与其他六个也来投奔刘邦的人一起见到了刘邦。
刘邦此时正在招兵买马，对于各类人才的投效都极为欢迎，见到七人入内，便命人准备酒菜热情款待。待他们吃完后，又吩咐人将他们带到客舍去休息。
陈平好不容易见到刘邦，哪肯放过这个好机会，连忙说道，“我有要事前来，所说的话错过今日就迟了”。
刘邦听罢，便将其留了下来，与陈平独自交谈了一番。一番交谈下来，刘邦发现陈平确实很有才能，顿时起了重用招揽之心，因此问道，“你在楚军时担任的什么官职？”
陈平回答道，“担任都尉一职。”
刘邦闻言，二话不说，当场任命陈平为都尉，并让其充作自己参乘，担任护军都尉，负责督查各级将领。
得知这个任命，一众将领当场就不干了，一时间议论纷纷，抱怨道，“大王日前不过刚刚得到一个楚国逃兵，还不知道他的本领高低，就跟他同乘一辆车子，而且还让他来监督我们这些跟了他数年的将领？”
对于刘邦来说，由于麾下将领大多出自乡野，平日行事过于散漫，随着军队规模越来越大，各级将领越来越多，管理难度越来越大，因此必须有人协助他来约束军法，明确上下尊卑，以规范军队的统属。
然而，汉军之中的将领互相熟络，又少有文化，要让他们来互相监督很难起到作用，如今任命新来陈平的人来完善军法、监督他们，岂不是事半功倍？
因此，当刘邦得知将领们的议论后，非但没有撤销任命，反而更加宠信和支持陈平，以确保他能对将领们真正起到监督作用。
更为很重要的是，刘邦从陈平口中得知了楚军的具体动向，在得知项羽主力仍被牵制在齐地，而西楚境内兵力空虚的情况后，刘邦遂决定一鼓作气攻灭西楚。
于是，在修武短暂休整后，刘邦自平阴南渡黄河，率领大军抵达洛阳。
刘邦刚刚到达洛阳，新城三老董公遮便前来拜见刘邦，先向刘邦诉说了义帝熊心被杀的经过，然后说道，“我听说‘顺德者昌，逆德者亡’，‘兵出无名，事故不成’。因此说：‘明其为贼，敌乃可服。’如今项羽大逆无道，驱逐并弑杀其主，实乃天下人都痛恨的逆贼。仁德之士不逞一时之勇，正义之军不拼一己之力。大王您应该率领三军着素服，将项羽的暴行通告全体诸侯，与他们一起讨伐项羽。如此一来，四海之内将没有人不仰慕您的德行，这才是像三王那样的仁义之举啊！”
董公遮一番话令刘邦茅塞顿开，于是在洛阳隆重祭奠义帝，亲自执礼哭祭，又命三军全体举哀三日，然后派遣使者通告各地诸侯道，“天下共立义帝，我们都是他的臣子。如今项羽驱逐杀害义帝于江南，实属大逆不道！寡人将出动关中所有兵马，聚集河南、河东、河内三地所有壮士，与诸位大王一起攻打楚国，诛杀项羽，为义帝复仇。”
刘邦檄文传到各国，立即得到了不满项羽的诸侯响应，西魏王魏豹复书表示愿意跟随，刘邦于是让其发兵相助。赵相陈馀则表示只要刘邦杀了张耳，自己就出兵相助，刘邦不忍，便杀了一个面貌与张耳相似者，割下首级送给陈馀，陈馀信以为真，于是也发兵南下。
同时，刘邦抽调关中的周勃、樊哙、夏侯婴率军至雒阳会合，又汇集了河南王申阳、殷王司马卬、赵王赵歇、西魏王魏豹、常山王张耳、韩王韩信等六路诸侯王的兵马，合计兵力五十六万，准备东进讨伐项羽。