刘邦向西撤退，路过梁地到达虞县。现在的形势对刘邦很不利，如果项羽继续追来，以汉军现在的残兵败将，很可能被楚军一路赶回关东甚至是消灭。
刘邦心灰意冷的对左右说：“你们这样的人啊，真是不足与之共谋大事！”谒者（负责传达通报的官职）随何说：“大王这是何意？”刘邦说：“谁若能说服九江王英布举兵叛楚，项羽肯定会留下来攻击他。如果能以此牵制项军几个月，我定能夺取天下。”
随何主动接下了这个任务，带着二十人前往淮南国。随何一行人在淮南国三日未得见到英布，于是对太宰（主管酒食的官职）说：“大王不见我，必然是认为楚强汉弱，这正是我来的原因。我若言之有理，则可请大王听之，若言之无理，我等二十人引颈待戮，以表大王之背汉亲楚。”英布于是同意接见随何。
随何对英布说：“汉王派我来递交国书与您交好，但我很奇怪您为何与楚国走的很近。”
英布说：“寡人不过是面北而事之。”古代帝王一般坐北朝南，英布此言意味以臣子的身份对待项羽。
随何说：“大王与项王同为诸侯，能屈尊面北而事，必然是因为楚国强大，可以依靠。然而楚军深陷齐国战争，您只派出了四千人马支援；楚汉对战于彭城时，您更是没援助一兵一卒，而是作壁上观，这样是面北而事吗？您不过是以这样的名义，保全自己，我认为这是不可取的。大王不背叛楚国，是您认为汉还不够强大。然而楚国身负背约和杀义帝的不义之名，它的强大不过是被军事实力衬托出来的而已。汉王联合天下诸侯，固守成皋、荥阳，背靠蜀汉之地的粮草，坚守要塞。若楚军来攻，不但要劳师远征穿越梁地，而且供给线长达千里。只要汉军坚守，则楚军必然进退两难。即使楚军获胜，天下诸侯马上就会人人自危而相互联合，这样的话楚军如何抵抗呢？所以，局势已变，楚不如汉。大王为何不联和蒸蒸日上的汉军，而是要依靠江河日下的楚军呢？我认为大王糊涂啊！虽然目前淮南之兵力不足以抵抗楚国，但大王只要发兵叛楚，就必然会牵制项王。如此只要数月，汉王即可夺取天下。彼时，若大王仗剑归汉，汉王必然给您分封一大块土地，淮南也肯定是大王您的。汉王派我来向大王进献上述愚计，请您定夺。”随何口吐莲花，说的英布连连称是，于是秘密答应了随何的计策。
当时楚国使者也在淮南国，催促着英布快快发兵支援。随何直接闯进来说道：“九江王已归汉，楚是得不到援兵的！”这当时就把英布吓了一跳。楚国使者起身想离开，随何对英布说：“我们既已经达成盟约，就必须要杀掉这个人，不能让他回楚国，同时还要马上发兵攻楚。”英布立刻全部照办。
项羽派出项声、龙且抵御英布军，自己攻打下邑。两方对峙果然持续了数月，最后英布败给了龙且，与随何从小路返回汉军。随何连哄带逼的说服英布叛楚归汉，使得刘邦的战略得以实现，极大的帮助了处于困境中的汉军。
汉二年五月，刘邦屯兵荥阳，萧何将关中五十六岁以上和二十三岁以下的老弱都派来前线参军。韩信也收拢兵马到荥阳与刘邦会师，汉军又恢复了元气。
这里简单阐述一下荥阳的地理位置和军事价值。荥阳东有鸿沟连接淮河、泗水，北依邙山毗临黄河，南临索河连嵩山，西过虎牢关接关中，地势险要。秦始皇很早利用这里的漕运资源，设置了大规模粮仓敖仓，解决了军队的后勤补给问题。因此在冷兵器时代，荥阳历来都是兵家必争之地。刘邦要想守住关中，就必须首先在荥阳设防，而项羽要想攻入关中，也只能从荥阳进入函谷关或通过南边的武关-崤关进入咸阳。
汉军与楚军在荥阳以南的京县和索县大战，取得大胜。随后修筑运粮的甬道通向河边，便于获取敖仓的军粮。
甬道是秦始皇发明的，就是左右两侧封闭的道路，可用于天子通行，外人无法看到里边。这里筑甬道是为了保障军粮运输的安全。敖仓也是秦始皇在敖山上设立的大粮仓，以备不时之需。汉军夺得敖仓并打通粮道，具有极为重要的战略意义。
六月，刘邦回到栎（yuè）阳，六月初六，立太子，赦罪人。当时的立储制度基本还遵循着“立嫡以长不以贤”的原则，且刘邦仅有嫡子一人，所以刘盈当之不让的成为了太子。储君为国之根本，司马迁在《史记》中就暗喻过太子的重要性，并把未立太子视为秦朝灭亡的重要原因。秦始皇没有明确太子，才导致他死后扶苏、蒙恬被奸相赵高矫诏赐死，而后赵高扶持胡亥即位，直接导致了秦朝的灭亡。
刘邦又命诸侯之子在关中的都集中到栎阳为守卫。这是常见的政治手段，以子为质来牵制诸侯们。这一系列的动作都表明，刘邦要排除所有不安定因素，全身心的投入到夺取天下的斗争中。
随后，汉军以水攻废丘，迫使废丘投降，章邯自杀，雍地八十余县就此平定。塞王司马欣、翟王董翳已投降项羽，此番章邯又自杀，关中三秦之地彻底被汉军控制。刘邦令官员组织对天地山川等进行祭祀，并安排定期举行。同时还组织关中士卒驻守边塞。
但经此战乱后，关中发生了大饥荒，粮价暴涨，甚至出现了人吃人的现象。此时，萧何苦心经营的蜀地、汉中大后方就起到了关键作用，成为了关中百姓的粮仓。
在刘邦屯兵荥阳之际，已投降刘邦的魏王魏豹谎称亲人有疾病需回去探望，但回到魏国后就立刻封锁了黄河渡口，倒戈投降了项羽。
楚怀王曾授兵于魏豹数千人，魏豹用这些军队平定了魏地二十余城，被项羽立为魏王。项羽入关后，改封魏豹为西魏王，都平阳。刘邦还定三秦，魏豹投降汉军，并跟随刘邦一起向东攻楚。这次彭城一战刘邦惨败，魏豹又倒向项羽一方。所以魏豹是不折不扣的墙头草，为图自保，谁实力强就投降谁。
魏豹叛汉还有一个有意思的理由。魏豹有一名妃子叫薄姬，相面先生许负说她是能够生天子的，魏豹大喜，认为自己是帝王命，于是就想要脱离刘邦寻求自立。事实证明，许负说的没错，薄姬确实生了天子，不过是为刘邦生的刘恒，即大名鼎鼎的汉文帝。魏豹只是自命不凡的空欢喜了一场，后面还因此搭上了自己的性命。
八月，刘邦处理好太子和章邯的事后，从栎阳回到荥阳。对于魏豹这样的人，刘邦本不想牵扯自己太多的精力，于是对郦食其说：“你若能说服魏王豹投降，就以魏地万户封与先生。”
郦食其到魏豹处转达了刘邦的意思，魏豹推辞说：“人生一世，如白驹过隙。如今汉王待人轻慢，对待诸侯就像对待自己的臣子一样，说骂就骂。十分无礼，我不想再见到他了。”这是十分幼稚的理由，魏豹再次降楚只是简单的因为他觉得跟着刘邦没有前途罢了。
这当然骗不了郦食其。因为郦食其本人是亲自体会过刘邦的轻慢辱人，但马上又被刘邦的魅力征服。郦食其回报后，刘邦立刻命韩信为左丞相，与曹参、灌婴共同攻魏。得知对方的大将、骑将、步卒将分别是柏直、冯敬和项它，刘邦放心的说，这三个人不是韩信、灌婴和曹参的对手，不足为虑。
魏在蒲坂屯兵设防，同时阻塞黄河渡口临晋。韩信故布疑兵，佯装要从临晋渡过黄河，而主力部队用木翁、木盆等简易工具从北边的夏阳渡过黄河，袭击安邑。魏豹大为震惊，马上带兵向东迎击韩信。韩信大败魏军，俘虏了魏豹。面对这个昔日叛将，刘邦并没治他死罪，而是再次接纳了他。
韩信派人向刘邦说：“请大王再为我增兵三万，臣便可北定燕赵，东击齐国，南断楚军粮道，再向西与大王会师于荥阳。”刘邦立刻为韩信增兵，并派张耳前来帮助。
在韩信的指挥下，代地很快也被平定了，丞相夏说被擒。这时，刘邦调回了派给韩信的军队，以增强荥阳守备。
刘邦虽然在彭城惨败于项羽，损失巨大，但由于英布的叛楚投汉，减缓了项羽西进的速度，给汉军创造了缓冲的时间。再加上后有萧何筹集兵源，前有韩信攻城略地，刘邦的实力又重新恢复了起来。