至南郑，诸将行道亡者数十人，信度何等已数言上，上不我用，即亡。何闻信亡，不及以闻，自追之。
——《史记·淮阴侯列传》
汉元年（前206年）四月，天下分封已定，各路诸侯于戏下会盟之后，开始陆续返回封地，张良亦决定继续辅佐韩王成重塑韩国，因而向刘邦告辞，刘邦虽然不舍，却也不好强迫，便赐其金百镒、珠二斗。
张良接受了刘邦的馈赠，但转手便将这些财物全部赠给了项伯，希望他能劝说项羽将汉中郡也封给刘邦，并称只有这样刘邦这个汉王才算名正言顺，更何况此时郦商已经攻克汉中。
项伯于是便去劝说项羽，项羽虽然心中不喜，但鉴于刘邦实际上已经控制了汉中，便也点头答应了下来。于是，刘邦得以掌控汉中郡、巴郡、蜀郡三郡之地。
刘邦虽然心中不忿，但在诸侯各自归国的情况下，他也不得不考虑入蜀之事。而在此之前，为了提振士气和收拢人心，刘邦决定对西进灭秦以来的有功之臣予以奖赏，于是樊哙、周勃、曹参、夏侯婴、陈豨、靳歙、周緤等十余位或多次先登、或斩杀秦军甚众的将领被赐爵为侯，萧何也因长期坐镇后方梳理政务有功，被刘邦任命为丞相。
封赏完毕，刘邦开始率军南下封地，而项羽为了防止刘邦不服分封，只允许刘邦率领三万人南下，刘邦无奈只得挑选了三万精兵，遣散了其他军队。
张良一路相随至褒中（今汉中勉县褒城镇一带），在此向刘邦告别，表示自己要就此返回韩国，辅佐韩王韩成。
临别之际，张良见一路行来，沿途多是悬崖峭壁，往往只有栈道可走，便对刘邦说道，“汉王何不烧毁栈道，如此即可表明再无东顾之意，消除项羽的猜忌，同时还可防备他人尾随袭击。”
刘邦认为张良言之有理，当即采纳了他的意见，派人烧毁沿途栈道，接着便上前握着张良的手说道，“今日一别，不知何日才能相见，先生也要多保重才是”。
两人依依惜别之后，刘邦继续南下南郑，张良则启程向东，沿汉水一路东行，前往韩国辅佐韩成。
张良不知道的是，就在他送刘邦南下汉中之时，范增得知项羽又将汉中郡封给了刘邦，连忙进谏道，“刘邦求取汉中，可见其贼心不死，虽说其北出之路已被堵死，却不得不防其东出南阳。南阳一带乃是韩国故地，而韩成、张良又与刘邦来往甚密，一旦使其东出，必成大患”。
项羽听罢，也顿觉后悔，不过事已至此，自然也不好反悔，思来想去，项羽还是觉得将南阳、颍川两郡掌握在自己手中方才安心。
当时，南阳郡虽然并未分封诸侯王，但却被刘邦实际占领，因此韩王韩成受封的颍川郡便成为了阻止刘邦东出的关键。于是，项羽便以韩成没有军功和张良从属汉王刘邦为由，不许韩王韩成返回封地，而是强行要求其跟随自己前往西楚，韩王成无力反抗，只能被迫跟随。
项羽在率兵返回西楚的同时，便派人先行一步，将义帝熊心迁往了当时还是南蛮之地的郴地（今湖南郴州）。熊心虽然不甘心，但也知道自己已经无法再辖制项羽，只得无奈地接受这个现实，但其麾下大臣却因多出自楚地，不愿远离故乡，故而拖拖拉拉不肯速迁。
当项羽已经快抵达彭城之时，得知仍有不少大臣赖在彭城不走，一怒之下便暗令九江王黥布、衡山王吴芮和临江王共敖，在义帝熊心的迁徙队伍途经他们封地之时，将其处死。后因截杀没有成功，项羽又派英布沿途追杀义帝熊心。
张良返回韩国后，得知韩王韩成已被项羽挟持至彭城，担心韩王有失，也连忙尾随而去。
项羽虽然只许刘邦率兵三万南下，但当刘邦踏上南下汉中之路后，却有不少楚国和诸侯国中因为敬慕而自愿跟随者，纷纷投入了刘邦麾下，前后多达数万之众，其中既有此前背叛刘邦，后成为赵将的雍齿，也有在项羽麾下郁郁不得志的郎中韩信。
韩信本是东海郡淮阴县人，少年时便自视甚高、志向远大。不过，由于家中贫困，而韩信又不事生产，整天在外蹭吃蹭喝，故而被乡邻所瞧不起，从这一点来讲，甚至还不如早年的刘邦。
秦末天下大乱，在项梁于率军渡过淮河北上时，韩信便也仗剑离开家乡，投入了项梁军中，虽然先后随着项梁南征北战，但却始终默默无闻。项梁战死定陶后，韩信便又归入项羽麾下，虽被任命为郎中，却仍然不得重用，韩信曾多次给项羽献计，但皆未被采纳。
项羽分封、诸侯会盟之时，韩信听说了刘邦的事迹，认为刘邦应该有雄才大略，而且身边人才济济，想必是个知人善用之人，于是便趁诸侯各自归国之机投效了过来。不过，由于刚刚投效的原因，韩信并未获得面见刘邦的机会，而只是被任命为了连敖，负责管理仓库。
就这样，韩信一路跟着刘邦的队伍南下，结果不久韩信便因犯罪被判处了死刑，要与其他十余人一起被处斩。
就在韩信即将被杀之时，突然见到夏侯婴从旁路过，连忙喊道，“汉王难道不想得到天下吗？为何要杀掉壮士。”
夏侯婴闻言，便制止了士兵的行刑，上前仔细查看，见韩信果然有些不同凡响，便上前亲自解绑，将其拉到一旁仔细盘问，一番交谈下来，感觉韩信此人的确拥有大才，而且犯的罪也不算太大，便跑去见刘邦，求情的同时也向其推荐了韩信。
对于夏侯婴等一帮老弟兄，刘邦还是十分信任的，而且韩信所犯之罪的确不大，刘邦便赦免了其死罪，并任命韩信为治粟都尉，负责管理大军的粮草。韩信在任上倒是恪尽职守，将大军粮草管理的井井有条，但也仅此而已，并未表现出有什么大才的潜质，刘邦便也渐渐将此事抛到了脑后。
当时，萧何作为刘邦的左膀右臂，主要负责后勤管理事务，乃是韩信的顶头上司。苦无施展才能的地方，又不甘心碌碌无为的韩信，便只能通过向萧何展露才能，希望通过萧何取得刘邦的重视。萧何经过长期与韩信的接触，也看出韩信不是常人，便也跑去向刘邦推荐，但仍然没有引起刘邦的重视。
辗转两个多月，刘邦终于率领大军终于走出了重重山谷，来到了汉中郡的治所南郑县，就此打算在南郑安顿下来，积蓄力量再图后事。
虽然刘邦入蜀之时，解散了大部分征召的新军，只率领了三万多嫡系军队南下，但由于这些将士大多来自于楚地，他们并不愿意长期离开家园，再加上两个月来的艰苦跋涉，便让很多人产生了逃跑的念头。南下途中，由于道路难行且栈道已毁，这些人还无法逃跑，如今到了南郑，向东便可经汉水一路进入楚地，于是不少将士开始偷偷逃亡。
一天，韩信见萧何等人多次推荐，刘邦仍然不对自己予以重用，心灰意冷之下，便也趁夜逃离了军营，打算另投明主。萧何得知消息，立即放下手中尚未处理完的公务，也来不及向刘邦禀报，便连忙带人策马去追。
刘邦不是不知道这些天来将士的逃亡，他虽然也恼火，但对此却也无可奈何，直到军吏前来禀报萧何逃亡，刘邦这才大怒，立即派人前去寻找。
两天之后，终于将韩信劝回来的萧何，回到军营后便立即跑去见刘邦，刘邦得知萧何回来，那是即高兴又生气，见了面便劈头盖脸的骂道，“你不是跑了么？又回来干什么？”
萧何连忙解释道，“我哪里是逃跑啊，我是去追逃跑的人。”
刘邦哪里肯信，便问，“你去追谁了？”
萧何回道，“韩信呗。”
听到这个名字，刘邦想了想，终于想了起来，没好气的说道，“各级将领跑了几十个人，你都没有去追，韩信不过一个小小的管粮官，你去追他？”
萧何说道，“诸将易得，国士难寻，这韩信可是真正的无双国士啊。如果你只打算做个汉中王，韩信这种人当然用不上，但是如果想要争夺天下，韩信这种人就绝对不能错过，除了他也没有可以商议对策的人了。就看你怎么选了。”
刘邦听罢，没好气的道，“我当然打算东出了，哪能一直憋在这个地方。”
萧何便上前说道，“如果您真的志在天下，那就一定要留下韩信，不过您只有重用于他，他才会留下；如果不对他予以重用，他还是会跑掉的。”
刘邦看了萧何一眼，说道，“看在你的面子上，就让他做个将军吧。”
萧何摇了摇头，说道，“虽说将军这个职位不低，但恐怕还是无法让韩信留下来。”
这下刘邦倒是有些吃惊了，狐疑的问道，“难不成让他做大将军？”
萧何连忙道，“如果真让他做大将军，那么他必然留下来”，顿了一顿，萧何又看着刘邦说道，“大王您一向傲慢无礼，如果随意就任命他为大将，恐怕他还是会跑。如果您真心想要拜他为大将军，还是应该郑重一些，选个好日子，搭设拜将台，然后事先斋戒沐浴，严格按照拜将的礼仪那样才行。”
见萧何说的郑重，不像是在开玩笑，刘邦也正色了起来，对着萧何说道，“我倒不是信不过你，只是任命大将军不是小事，至少也应该先让我见识见识他的才能吧。”
萧何见刘邦已经松口，便笑着道，“这有何难，我将他找来，你考他一考便是。”
说罢，萧何走了出去，将在外等候的韩信带了进去，然后三人就此坐而论兵，从用兵之事谈论到天下大势，这一谈便是整整一天。
一番交谈下来，刘邦这才意识到韩信果然有大才，当场表示要拜韩信为大将军，并立即命人搭建拜将台和铸造大将军印。汉军将士们听说刘邦要拜大将军，一时间也是众说纷纭，尤其是那些立下汗马功劳的将领们，更是纷纷认为自己便是大将军的不二人选。
之后，刘邦按照萧何的建议，郑重斋戒沐浴，数日之后正式举行拜将仪式，将大将军印郑重的交到了韩信手中，而当汉军将士们看到登上拜将台的是一个没几个人见过的新面孔后，一时间全都被惊掉了下巴。