据《史记·萧相国世家》记载：“及尚祖起为沛公，何常为丞督事。”按楚国制度，县宰称“公”，故刘邦起兵占据沛县，称“沛公”，而“丞”则是各级官吏的主要助手，如郡丞、县丞等。萧何自跟随刘邦起兵后，“常为丞督事”，是说他在沛公南征北战直至兵入关中这段期间内，萧何一直是作为沛公的主要助手，负责掌管沛公这支起义军的一切政务，其工作是相当繁杂而艰巨的。由于当时主要是行军作战，萧何所掌管的政务亦是为作战服务，因而他在这一期间的活动和功绩，史书没留下具体的记载。
萧何以他卓越的才华赢得汉王的信赖，以至汉王到汉中第一件事便是任命萧何为相。在南郑的汉王府，汉王刘邦步出府门，环顾四周远方的高山，这时他才对汉中这块盆地有所体会。几万大军进入汉中，然而这狭小的汉中盆地却不可能成为将士们的用武之地。此时他佩服萧何在关中为他所制定的“养其民以致贤人，收用巴蜀”的路线是何等的英明而准确。这时，汉王认识到目前的首要任务是安定秩序，发展生产，招纳贤才，制定各项制度，征收赋税，总之，是积蓄力量，养精蓄锐，准备“还定三秦”。而这个中心任务，主要落在萧何的肩上。
萧何在秦时任沛县主吏，早已显示出不平凡的才华，因而当时泗水郡的郡监想要把他推荐到朝廷做官，但被萧何推辞。经过几年的战争风雨，特别是在咸阳收缴了秦王朝的档案文书之后，对于如何治理好汉中，“养其民以致贤人，收用巴蜀”，萧何早已有所考虑，成竹在胸。至于萧何到汉中后在丞相职务上都制定了哪些制度，做了哪些工作，史书没有留下具体的记载，但不外乎他在关中时所谈到的三个方面：
一是“养其民”，在关中及巴蜀地区安定秩序，发展生产，积蓄力量；
二是“收用巴蜀”，派官员到巴、蜀二群安定秩序，发展生产，征收巴蜀二郡的赋税作为军资，从巴蜀征召士卒以补充兵员；
三是“致贤人”，为汉王发现和推荐人才。在这方面，萧何所做出的巨大贡献是向汉王推荐韩信为统兵大将。
韩信是汉王刘邦夺取天下所依靠的三位“人杰”之一，在楚汉战争中起到了举足轻重的特殊作用。因而有关韩信的身世以及萧何荐举韩信为统兵大将的许多生动故事，一直广泛地流传于民间。
据《史记·淮阴侯列传》及《汉书·韩信传》的记载：韩信是淮阴（今江苏淮阴市西南）人，出身于平民家庭，品行又不怎么好，未能被推选到官府去充当官吏，又不肯务农或经商，因而经常是投靠他人吃闲饭。韩信的母亲病死，没有钱安葬，他便找一块四周广阔的高地为坟，使令坟地的周围可以安置万家。韩信的这一举动，表明他青年穷困时期便胸怀大志，自信将来能显贵，受封王候，因而预先为死去的母亲选择了这样一处四周可供万家守冢人居住的高大坟地。
韩信这种吃他人闲饭的日子并不好过，很多人都讨厌他。韩信寄食时间较长的是淮阴下乡的南昌亭长家。南昌亭长见韩信虽然没有个正当职业谋生，但举止又不与一般青年人相同，整日少言寡语，若有所思，也就听任韩信寄食。几个月过后，亭长的妻子开始讨厌韩信，便清晨提前吃饭，待韩信按往常开饭时间到达时，人家已吃完，不再为韩信准备饭食。韩信明白了女主人的用意，一怒之下，他再也不到这位亭长家去寄食了。
韩信失去吃闲饭的去处，便到城下河边钓鱼。河边有很多老大娘在那里冲洗丝棉，其中一位老大娘见韩信饿成那个样子怪可怜的，便把带去的饭食分给他吃。就这样，韩信一连“数十日”都是吃老大娘分给他的饭食，便感激地说道：
“日后我必定重重报答您老人家。”
老大娘却怒气冲冲地训斥了韩信一通：“男子汉不能自食其力，还不知道羞耻，我哪里稀罕你的报答？”
韩信平时常带剑行走在街上，屠户中有个少年无赖见韩信经常大模大样地佩剑在街上走来走去，瞧着不顺眼，便存心想侮辱韩信。一日，少年见韩信迎面走来，便故意拦住去路，油腔滑调地向韩信说：“你看看你，虽然长个大高个子，又好佩带着刀剑走来走去，可心里却是个胆小鬼。”
少年无赖在闹市上向韩信无理取闹，顿时有很多行人围上来观看。少年见围观的人多了，更是增添了几分精神，便当众扯开衣襟，露出胸膛，用手比划着对韩信说：“来，你若是不怕死，刺我；若是怕死，就从我的胯下爬过去。”
韩信用鄙视的眼光直盯着这个无理取闹的无赖，觉得可笑可怒。他本可以抬脚把这个无赖踢出几丈之外，转念间想起《孟子》书上说过的“匹夫之勇敌一人”、“武王一怒而安天下”、“视不胜犹胜也。”韩信觉得这正是修身养性的机会，再次用目光打量一下眼前这个少年，便弯下身子，趴在地上，从少年的胯下爬了过去。市街上围观的人见此情景，无不嘲笑韩信，都以为他是个胆小怕事的人。
待到项梁在吴中起兵反秦，大军渡过淮河，韩信认为施展抱负的时机已经到来，便手持宝剑投奔于项梁的部下，可是，没有等到显露出什么名声，项梁就战死了，后来隶属于项羽，项羽让他做“郎中”，负责警卫工作。由于职务上的方便，韩信多次就军务大事向项羽献策，高傲自大的项羽根本没瞧起这位小小的郎中，怎能听得进他的献策？
韩信随从项羽的大军到达关中，在项羽分封诸侯、各诸侯王分别就国时，韩信因不得项羽重用，便在汉王入汉中时偷偷离开楚军大营，投奔到汉王刘邦的部将夏侯婴的部下。夏侯婴做过滕县县令，因而人们称他为滕公。在滕公部下，韩信一时也未能显露名声，只是担任“连敖”职务，不过是个负责接待官吏的小官而已。一次，因触犯军法而被判处斩刑，同案的13人均已行刑问斩。依次轮到韩信，韩信抬头仰视，正好看见滕公，便大声说道：“汉王不是想成就夺取天下的大业吗，为什么斩杀壮士？”
滕公闻听韩信出言不凡，又见他相貌威武，便释放韩信免他一死。滕公与韩信交谈，十分高兴，并把这一情况向汉王汇报，汉王任命韩信为治粟都尉，负责管理全军的粮饷，但汉王并没有看重他。
韩信出任治粟都尉后，有机会多次和萧何促膝长谈，萧何认为韩信是不可多得的人才，虽然萧何也多次向汉王推荐韩信，但仍然没有被重用。于是韩信又选择了在一天夜晚不辞而别！
萧何得知韩信逃亡，感到事情重大而紧急，来不及向汉王汇报，立即乘马按照人们所指示的方向连夜追去。丞相府的人找不到自己的长官，不得不向汉王禀报，说丞相逃亡，不知去向。汉王听说丞相萧何逃亡，如同失去了左右手，又急又怒。第二天的傍晚，马不停蹄地追赶韩信的萧何，终于在路旁的小酒店门前发现了韩信的坐骑。在小店内饮酒的韩信，发现丞相闯了进来，身边没带一名随从。看丞相风尘仆仆的样子，眼睛布满了血丝，心里便明白了大半。韩信急忙起身施礼，并机警地步出店门向四周张望，发现丞相的坐骑汗如水洗，四蹄颤抖，周围空无一人，一片寂静。此刻，韩信一切都明白了。他为丞相不顾疲劳地连夜追赶自己而深受感动。两人并没有说什么。韩信请丞相坐下休息用餐过后，两人携手步出酒店。二骑并行，一路回奔南郑。路上，两人也没有更多的话语，也许是在一天一夜的紧张和劳累过后，他们都已经很疲倦了。
第三天，萧何在回到南郑后，立即到汉王府拜见汉王。汉王见萧何不待寻找而自行回来又喜又怒，骂道：“你深夜逃走，是何缘故？”
“臣不敢逃亡，臣是去追赶逃亡的人。”
“你是去追赶何人？”
“韩信啊。”
汉王听丞相说所追赶的是韩信，大惑不解，以为丞相在骗他，因为不久前也有诸将逃亡过，所以汉王开口骂道：“诸将领逃亡的有10多人，您都不去追赶；说什么追赶韩信，这是扯谎。”
萧何说：“大王，那逃亡的诸将，都是容易得到的人，而韩信则不同，他这么杰出的将才，普天下找不出第二个啊！大王如果想称王汉中，韩信派不上用场，可大王如果是想争夺天下，非韩信不可与您共商大事，就看您怎么决策了！”
汉王这才想起丞相曾多次谈到韩信的才能，自己总是没有当回事，这次见丞相不待禀报连夜把韩信追赶回来，感到韩信如不是真的有些本事，丞相怎会如此器重他。想到这里，汉王便心平气和地回答丞相的发问：“我当然是想要向东发展，不想总是闷闷不乐地呆在这里。”
“大王如果是决计东征，能重用韩信，韩信会留下来；如不能重用韩信，他迟早还是要逃亡的。”
“我要任命他为将。”汉王说。
“虽任命为将，也不一定留得住韩信。”萧何答。
“那我就任命他为大将。”
“这可太好不过了！”
于是，汉王便要派人召见韩信，拜他为大将。这时，萧何赶忙阻拦说：“大王向来对部下傲慢无礼，今日任命大将像召唤小孩子一般，这正是韩信之所以离去的原因啊。大王如果决心任命韩信为大将，要选择个良辰吉日，事先斋戒，设立拜将的高坛和广场，拜将的礼仪要隆重而完备，如此方才可以。”
于是汉王采纳了萧何的建议，向全军宣布了此命令。此项命令宣布后，全军一片欢腾。且不说那些士卒们想要知道谁会被拜为大将，光是观看从未见过的拜将典礼究竟是个怎样的场面，也算开开眼界了；而那些跟随汉王转战南北、屡建战功的将领们，更是抑制不住内心的喜悦。有不少将领都认为自己的战功最高，盼望着届时被汉王任命为大将。
直到举行拜将典礼的前夕，究竟谁会被任命为大将，这对全军将士们来说仍然是个谜。
6月的一天上午，南郑城中的练兵场上，四周的无数面赤色军旗迎风招展，手持长戟的卫士笔直地站在校场的四周。校场的北面是新建筑的拜将高坛，坛下有持戟卫士把守。清晨，参加典礼的兵卒列队入场；不久，众将领也都陆续来到坛场，依次立于高坛之下，面坛而立。
时辰一到，鼓乐齐鸣。此刻，汉王已坐于高坛的正席之上，面南而坐；丞相萧何坐于西侧，面东而坐。鼓乐过后，传令官在坛上高声宣读汉王命令。汉王有令：
“拜韩信为全军统兵大将，召韩信登坛受拜为大将。”
校场上的众将领听说拜韩信为大将，无不感到惊讶。他们都怀疑自己的耳朵是不是听错了，有的将领甚至不知道或没有见过这位毫无军功、并未曾统兵作战的治粟都尉。
韩信应声从行列中走出，威风凛凛地迈步登坛。这时坛场内顿时又鼓乐齐鸣，校场上的士卒们也都呼声如潮。至于韩信在坛上如何受拜为大将，坛下的众将领大多是没有兴趣。确切地说，是不屑抬头观看。韩信有什么本事能被汉王拜为大将，显然各位将领心存疑虑。无可奈何之下，众将领们也只好摇头退场，准备着看看这位大将日后怎样指挥全军。
