公元前二〇六年四月，项羽分封的诸侯王各自回归本国。汉军的将士本以为从此可以在关中享受舒服的生活，没料想却要西去偏远的巴蜀。于是，大家在行军途中唱起了思乡曲，有的将士干脆“走为上计”。
一天中午，刘邦刚吃过午饭，忽然有人报告：“丞相萧何逃跑了！”刘邦大惊且怒，“如失左右手”。当初，萧何在沛县做主吏掾(秦县令属吏，主管群吏进退)时，刘邦只是平民百姓并得到了他的处处照顾。后来刘邦做了泗水亭长，两人的关系就更铁了。
陈涉起义后，沛县县令打算举城响应。萧何说：“可以把那些逃亡在外的人召集起来，这才会有号召力。”谁知刘邦率众响应号召来到沛县城下时，县令又后悔了，下令关闭城门。萧何与曹参策动城中百姓，杀掉了县令，并敞开城门迎接刘邦，拥立他为“沛公”。萧何、曹参还为刘邦召集沛县青年三千多人，以响应诸侯抗秦。
萧何跟随刘邦进入咸阳时，将士们都奔向府库取金帛财物，萧何却进入丞相府尽收图集文献资料，从而“具知天下厄塞，户口多少，强弱之处，民所疾苦”。这些资料，为后来打败项羽发挥了至关重要的作用。
项羽背约，封刘邦为汉王，都南郑。刘邦大怒，想要攻打项羽，周勃、灌婴、樊哙等苦苦相劝，刘邦就是不听。这时，萧何劝道：“在汉中当王虽然窝囊，但总比死了好吧？”刘邦问：“怎么就会死呢？”萧何说：“如今咱们兵众不如项羽，百战百败，不死又能怎样？”他劝刘邦要像商汤王、周武王那样“能诎于一人之下而信(伸)于万乘之上”，立足汉中，养民致贤，“收用巴、蜀，还定三秦”，以图天下。于是，刘邦放弃攻打项羽的念头，并任命萧何为丞相，之后才一路西行。可刚到了南郑，萧何怎么就逃跑了呢？
刘邦起坐不安，饮食俱废，冥想了一天一夜，还是想不明白。就在这时，萧何突然进来了。刘邦“且怒且喜”地问：“你为什么逃跑啊？”萧何说：“我哪敢逃跑！我是追逃跑的去了。”“你追谁去了？”“追韩信。”刘邦笑骂道：“将领逃跑了数十位你不去追，却去追个治粟都尉韩信，纯粹是撒谎。”萧何说：“那些将领都很容易得到，但像韩信这样的人，却是天下无双！陛下如果只在汉中称王，自然用不着韩信。如果要争夺天下，除了韩信，可就没别人了。就看陛下怎么抉择了？”
刘邦回话：“我当然想要东进呀！问题是你举荐的这个韩信真有那么大的本事吗？有人听说他是个懦弱的胆小鬼，有人说他没什么谋生本领，经常去别人家蹭吃蹭喝。他从项羽那里过来，短短几天就连升两级，也可以了。如果用这样的人为将，不仅三军不服，而且诸侯也会讪笑啊！”
萧何说：“自古将相多出自寒微，岂可以门户论人？伊尹、太公、宁戚、管仲，都出身贫寒，后来都成就了大事。韩信虽出微贱，却满腹经纶。范增见而奇之，荐于项王，项王不识人，韩信这才弃楚投汉。愿陛下听微臣之谏，重用韩信，项羽可灭，咸阳可复。如负所举，可治臣之罪。”
刘邦说：“那我就看在你的面子上任用他做将军吧。”萧何说：“即便是做将军，韩信也不会留下来的。”刘邦说：“那好吧，你就去召韩信来，我任命他为大将军。”萧何说：“陛下向来傲慢无礼，现在要任命大将军了，却如同呼喝小孩儿一样，这就是韩信要离开的原因。你如果要授给他大将军官职，就请选择吉日良辰，沐浴斋戒，设坛拜将，举行盛大隆重的授职仪式。”于是，刘邦按照萧何的请求，拜韩信为大将，最终成就大业。
