憋了一肚子气的刘邦一入汉中，就立即抓紧时机整军备战，积极扩充实力。他任命萧何为丞相，负责治理国家。于是，萧何这个管家更加忙碌了，身上所肩负的责任也更加重大。
为了帮助刘邦及早回师关中与项羽争雄天下，萧何忙里忙外，制定相关措施，治理巴蜀、汉中，兴修水利，整治农田，鼓励农业生产，储备战略物资，征发适龄人员入伍，扩充军队，在各方面为刘邦的东进准备条件。在这期间，萧何为刘邦做了一件至关重要的事情，他为刘邦物色了韩信这位优秀的军事统帅。没有韩信，刘邦后来不可能战胜项羽。
这韩信原来是项羽手下的执戟郎中，曾经多次上书项羽向他进献良策，无奈项羽本人就是打仗的天才，在战场上百战百胜，对韩信的谏言不置可否。再加上韩信早年在淮阴市井贫困潦倒，连生活都不能自理，靠去别人家混饭吃过日子，经常被别人嘲笑，更让人看不起的是，有个市井无赖当众欺负他，说他带着剑装模作样，其实就是个胆小鬼，说韩信你有种就拿剑刺我，没种就从我的胯下钻过去。当着一市之人，韩信居然硬是从那家伙的胯下钻过去了。这不仅是个胆小鬼，简直就不是个男人。项羽非常看不起他的人品，心想，像这样的人也有资格去谈论什么军国大事？于是，从不理会他，甚至平常根本不拿正眼瞧他。虽然范增也曾多次建议项羽重用韩信，但是，项羽始终不为所动。韩信见自己在项羽那里看不到前途，永无出头之日，于是，就在刘邦前往汉中就国之际，他向项羽请辞，跟随刘邦去汉中。韩信满以为去了汉中就能得到刘邦的重用，因为他知道刘邦这个人是干大事的人，非常注重有才能的人，尤其是有治国用兵之才的人。但是韩信到了刘邦那里，在起先混得并不如意，他几乎见不到刘邦，有关人员比照他在项羽那边的职务，给他安排了“连敖”（负责搞接待工作的）一职。不过，是金子到了哪里都会闪光，不久，他的才能引起了夏侯婴的注意。这夏侯婴是跟随刘邦在沛县起兵的难兄难弟，而且在关键时刻敢于挺身而出为刘邦背黑锅，深得刘邦器重。于是夏侯婴便向刘邦推荐韩信，说他如何如何了得。不过，此时的韩信确实没有什么名气，也更没有指挥过一场战役，甚至连兵都没有带过，刘邦又怎么可能相信他是统帅之才呢？况且刘邦对于他的不雅名声也有所耳闻，于是便给了他一个治粟都尉的官，负责管理军队的粮草。
韩信做了治粟都尉后，自然要和全面负责后勤工作和处理政事的萧何有工作上的往来，在短暂的接触中，他的才能立即引起了萧何的注意，萧何认为韩信这个人不同凡响，是当今天下罕有匹敌的军事天才，于是当即向韩信保证要向汉王推荐他。
萧何没有食言，他几次在刘邦面前提起韩信这个人，说韩信这个人是当今天下罕见的军事奇才，应该对他委以重任。平心而论，刘邦对萧何的意见一向是非常重视的，而且萧何在沛县当主吏掾时，是负责人事和文书工作的，对人才的审视和鉴别自有其过人之处，他说某个人行，一般八九不离十。但是，三军统帅非同儿戏，怎么可能让一个名声那么不好，也从来没有过战场指挥作战经验的人来当呢？于是，刘邦对萧何说：“韩信这个人，夏侯婴也对我多次提起过，说他是个人才，如今丞相又亲自引荐，说明这个人确实有过人之处，不过，拜任三军统帅是大事，须从长计议，对韩信还需要进一步考查。”
韩信知道萧何已经向刘邦推荐了他，但是，好长一段时间过去了，汉王刘邦始终不提要重用韩信的事，韩信非常失望，觉得刘邦和项羽一样，对自己也有成见。于是，决定离开刘邦，另投明主，伺机干一番大事。一天夜里，韩信不辞而别逃离汉中，准备回到中原地区，再找一个有实力的诸侯王辅佐。
第二天早上，萧何听说韩信跑了，大惊，来不及告诉刘邦就骑马追了上去。幸亏当时汉中去关中的路就那么两条，而人们常走的只有一条，所以萧何快马加鞭，沿途不断换马，追了两天，终于在快到边境的地方追上了韩信。韩信当然不愿跟他回去，说回去了也不受重用，倒不如另谋出路。萧何说，如果这次回去汉王再不重用韩信，那么他也和韩信一道逃亡。韩信见萧何如此说，只得跟他一起回去。
萧何回去以后，刘邦又恼又喜，恼的是萧何不辞而别，喜的是他终于回来了。汉中的条件自然不能和关中相比，交通条件差不说，其他方面的条件也没有办法和关中、中原一带相比，比如居住条件、气侯条件、生活条件，甚至这里的女人也没有关中一带漂亮，这些天，有很多人吃不了那份苦，纷纷离开刘邦逃亡而去，刘邦正为这件事犯愁，偏偏手下人又告诉他萧丞相也逃走了。这下怎么得了，萧何是他最信任的人，连萧何都可以背叛他而去，那么谁还值得他相信呢？谁还会长期跟着他待在汉中呢？都跑光了，他又和谁一道挥师东进去与项羽争雄天下呢？况且萧何是他的左膀右臂，萧何一走，几乎所有的工作都要瘫痪下来，刘邦一时六神无主，不知无何是好。所以，刘邦一见萧何回来又惊又喜，劈头盖脸就骂：“你跑什么，你为什么要逃跑，寡人哪点对不住你？”
萧何连忙谢罪说：“请大王息怒，臣哪里敢逃，给我十二个胆子臣也不敢，臣这是追逃跑的人。”
刘邦听萧何这么一说，反倒有些感兴趣了，接着问道：“你追的是谁？是哪个混帐东西有那么大的能耐，能劳丞相大驾亲自去追他？”
萧何回答说：“是韩信！”
刘邦一听就气不打一处来，又是那个钻人裤裆的家伙，骂道：“我手下的重要将领逃亡了几十人，你一个也不去追，为什么偏偏要去追韩信？”
萧何回答说：“那些逃走的将领只是普通将才，多的是，到哪里都能抓一把，至于像韩信这种人才，天下没有第二个，绝对不能让他离开。当然，如果大王只想长期在汉中当王，那么韩信可能派不上什么用场。但是如果大王真的要想夺取天下，那么没有韩信肯定不行。要不要留住韩信，那就要看大王是想安心做个汉中王呢，还是做一个天下共主的真命天子？何去何从，全凭大王决断。”
刘邦一听，立即说：“我当然想挥师东进与项羽争夺天下，怎么可能一辈子呆在汉中这个鬼地方呢？”
“既然如此，那么大王为什么不重用韩信呢？没有韩信，你靠什么去和项王相争呢？请大王想一想，现在你手下的那些将领，哪一个是项王的对手，既然都不是项王的对手，你又如何去和项王争天下？”
刘邦见萧何这次是铁了心要他重用韩信，他知道自己惹不起萧何，要是让萧何失望，他也和韩信一样跑了，那么他真的做梦也甭想去和项羽争天下了。于是，他便问萧何：“那你看，寡人该封他做个什么官呢？”
萧何说：“像韩信这样的人，哪一个诸侯重用他，这个诸侯就能夺取天下，所以，大王封他做什么官都留不住他，除非让他做三军统帅，封他做大将军。”
“好，那就封他为大将军。”刘邦也很爽快，马上就命人草拟文书，准备下达任命，封韩信为大将军。
萧何看到刘邦一反常态，这样轻松地封大将军，简直是视封大将军如同儿戏，便郑重进言，要求选择一个良辰吉日，斋戒筑坛，正式拜封韩信为大将军。刘邦见萧何这样认真，只好满口答应。
于是，刘邦传下令去，命人筑起高台，选择良辰吉日，准备斋戒后登台拜将。
就这样，韩信成了刘邦的大将军。
刘邦拜韩信为大将军后，同韩信就天下大势进行了一番深入的长谈，韩信娓娓道来，将刘邦与项羽各自的优势和劣势进行了详细的对比，刘邦听得着了迷，茅塞顿开，连声叫绝，一个劲儿地向韩信致歉，说自己有眼无珠，不识大贤，没有及时委以重任。
韩信拜将，这是刘邦东进的序幕。在汉中的刘邦并不缺少敢于冲锋陷阵的猛将，像曹参、樊哙、周勃、灌婴等人都能担此重任，但是将在谋不在勇，在于善于掌控全局，把握战机，出奇制胜，这些人显然没有这个能力。而善于奇谋的张良此前已经告别刘邦随韩王成去就国，此时的刘邦正需要一位有深谋远虑的将才来帮他统御军队。而萧何作为刘邦的主要参谋，也深知自己并不善于军事，于是他不遗余力地向刘邦推荐韩信，并促使刘邦拜韩信为将，终于填补了刘邦在这方面的人才空缺。平心而论，在韩信的将才尚未经过实践验证的情况下，萧何就力主刘邦拜他为大将，显然具有很大的冒险性，但是在当时不冒这个险，就难以迈出第一步。毕竟跟随刘邦前往汉中的只有3万人马，而且由于不少人忍受不了汉中的恶劣条件，不断逃亡而去，如果再这样下去，那么等到部卒逃亡殆尽，而关中一带的力量又得以加强，项羽在东方已经打败反叛他的诸侯以后，刘邦要想向东与项羽争雄天下，那么就真的只有做梦了。而事实证明，萧何及时地举荐韩信，促使刘邦拜将，正是刘邦事业的一个重大转折。