刘邦领了汉中王的封号，带领军队及其他追随者前往封国，并烧毁栈道，意思是告诉项羽，我刘邦不会再回来了，给项羽吃了一颗大大的定心丸。但刘邦真的无意东归么，真的会把自己打下的关中拱手让人么？当然不是，只不过这个时候他还要继续积攒实力，寻找机会杀回来。此时，他遇到了军事奇才韩信，至此，“汉初三杰”已全部汇聚到了刘邦身边，他们将帮助刘邦定鼎天下
刘邦西去即将到达南郑，手下将领及士兵齐声唱着思乡之歌，都想回到关东故乡，甚至还有不少逃兵。当时韩信只是刘邦帐下管理军粮的都尉，也跟风逃跑了，萧何亲自把韩信追回，并把他推荐给刘邦，同时说：“如果汉王想要争夺天下，非与韩信共谋大计不可。”
韩信早年贫穷落魄，做官和经商都不行，经常到别人家蹭饭吃，母亲去世都无法很好的安葬。韩信曾在南昌亭长家混饭，久而久之，亭长的老婆十分反感，不得不早早的就做好饭，等韩信到的时候，全家已经吃完了。后来，韩信曾在河边向洗衣服的大娘乞食，又被同乡少年欺负忍受胯下之辱。
项梁军队路过淮阴时，韩信加入了楚军，正式开启了自己传奇的一生。项梁死后，韩信又继续追随项羽。韩信曾屡次向项羽献计而不得用，于是弃楚投汉，做了一个管理粮仓的小吏。后因犯罪被判死刑，行刑时，韩信看到滕公夏侯婴，于是大喊：“汉王不想做天子吗？为何要斩杀壮士！”夏侯婴见他出言不凡，相貌甚壮，于是刀下留人。经过交谈之后，发现这个人很有才能，于是就推荐给了刘邦。韩信这才在汉军中获得一个管军粮的都尉之职。夏侯婴是韩信的第一个伯乐，让他得以逃脱死刑，进入军中供职。
有了这样的职位，韩信才能获得跟萧何交流的机会。几次交流下来，萧何发现这个人非常有能力，于是才有了前面追韩信的故事。那韩信为什么要逃走呢，其实理由跟离开项羽差不多，他估计萧何已经跟刘邦推荐过自己几次了，但没有音信，所以才想跑。但刘邦不同项羽，因为他帐下有萧何这样的伯乐。
萧何追出去后，有人就跟刘邦汇报，“丞相也跑了！”刘邦大怒，仿佛失去了左右手。一两天后，萧何回来了，刘邦又怒又喜，骂萧何：“你为什么跑？”萧何说：“我哪敢跑，我是去追逃跑的人的。”刘邦又问：“你去追谁？”萧何说：“韩信。”刘邦刚骂完萧何还没消气，听到他是去追韩信的，火就又上来了，又开始骂：“军营里逃走的将领有数十人，也不见你去追，追一个小小的韩信，你他妈骗我吧！”萧何说：“那些将领跑了还会有，但韩信不一样，他是无双的国士啊！汉王若只想稳坐汉中，有没有韩信也无妨，但如果想要争夺天下，则必要用韩信，请大王速速决定！”
刘邦说：“我倒是也想东进，谁愿意在这个破地方待着！”萧何说：“汉王既然要东进，那就好好用韩信，否则他还是要跑。”于是刘邦准备让韩信做将军，萧何说不行，刘邦说，那就让他做大将军，萧何说，这才能留住韩信。这是韩信的第二个伯乐，有了萧何力荐，才有后来在战场上叱咤风云的战神韩信。但后来，也是因为萧何，韩信被吕雉设计诛杀，即所谓“成也萧何败萧何”。
既然聊好了职位，接下来就是拜将的仪式了。本来刘邦就想把韩信喊过来，跟他讲一声就算了，但萧何很了解刘邦，说道：“大王素来傲慢无礼，如今拜大将如同儿戏，韩信还是得跑。必须要择日斋戒，布设坛场才行。”刘邦也是听话，估计还没见过韩信，就决定正式拜他为大将军。各位其他将领都沾沾自喜，以为自己要成为大将军，结果一看竟然拜的是韩信，全军震惊。
刘邦做足了场面，最后总归要问问韩信，看他到底有什么妙计。韩信说：“项羽违背怀王之约，把大王封于汉中，是一种贬谪。军中将士均为山东之人，日夜思乡望归，若利用这种锐气，则必能取胜。如果等到天下安定，百姓安宁了，就没有这个时候的士气了。不如现在就回师向东。”于是向刘邦陈述了击败项羽，夺回关中之策。刘邦听了大喜，便按照韩信的建议部署军务，把萧何留在巴蜀筹集钱粮。
韩信所献的计策被详细的记录在《汉书·韩信传》中，其实并无具体的军事部署，而是向刘邦陈述了一些汉必胜楚的原因。首先，韩信说，刘邦争夺天下的主要对手就是项羽。刘邦虽然勇猛不如项羽，但贵在懂得用人。项羽之勇，振臂一呼即可喝退千人，但不懂得用人，这便是匹夫之勇。项羽待人恭谨，言语和善，见人生病，便落泪并赐予食物。然而当属下立功当赏之时，所刻的大印在手中都要磨掉角了，还舍不得授予。而且分封天下时，不都关中而都彭城，又违背怀王之约，还不按战功多寡而按亲疏远近封王，诸侯十分不平。项羽驱逐义帝，诸侯见此都转投旧主，给自己分封好的地盘。除此之外，项羽打仗残暴无度，所过之处生灵涂炭，与百姓结怨，百姓只是不得不屈服。所以项羽虽名为霸王，实则失去了天下之心。如今汉王如果反其道而行之，任用天下勇将，何所不诛！用天下之地分封给有功之臣，何所不服！用道义统领思归之将士，何所不胜！韩信以三个何所总结项羽之劣势和刘邦之优势，可谓鞭辟入里，入木三分。
前面说的是天下大势，后面韩信继续阐述夺回关中所面临的的情况。关中之地被项羽封给了秦朝的三位旧将：章邯、司马欣和董翳（yì），这三人管理秦朝百姓数年，杀人无数，且秦军被项羽坑杀者多达二十余万，唯独这三人未死，秦地父老对其恨之入骨。汉王自进入武关以来，秋毫无犯，除秦苛法，约法三章，深得民心。百姓也知道“先入关中者为王”的约定，如今却被封至蜀地，百姓没有不怨恨的。如今汉王东归，是履怀王之约，不用一兵一卒即可收回三秦之地。
韩信洞悉天下，所言有理有据，刘邦闻之大喜，觉得与韩信相见很晚，于是下令，所有人听命于大将军韩信，同时令萧何筹备粮草，准备反攻关中。