張良也驚異於蕭何的淵博和遠見，進而極力讚同蕭何的觀點：“蕭何說得對，巴蜀是個好地方，沛公不妨前去，而且走得越快越好，早日離開這是非之地，範增日夜都在設計陷害沛公。隻是有一點：那裏雖然土地肥沃，易守難攻，卻沒有外圍作為緩衝，如能占據漢中，就會更加方便，沛公可以去爭取。”沛公搖頭：“向項羽要漢中太難了。”“可以請項伯幫忙。”張良建議道。劉邦就請張良去找項伯，委托這個大哥替自己討要漢中。
鴻門宴後，劉邦為感謝張良，送給他黃金百鎰、珠子二鬥（鎰是古代計量單位，每鎰為20兩）。貴族出身的張良視錢財如糞土，收下之後都轉送給了項伯。此時劉邦又湊集了一筆豐厚的財寶，仍請張良出麵賄賂項伯。項伯受張良所托，還有重金酬謝，何樂而不為？於是轉而對項羽說：“沛公想要漢中，我看大王給他就是。咱們違約在先，這次何不應他所請，也就算不虧待他了，也可以讓天下人都說大王分封公平。”
項羽隻求盡早結束這一切，趕快“衣錦還鄉”，隻要劉邦肯服從去巴蜀，區區一個漢中給他何妨？於是劉邦如願以償，除巴蜀之外，又得到了漢中。漢中與關中僅隔一座秦嶺，比起從巴蜀還定三秦顯然要容易得多。更何況，劉邦得了三郡之地，與僅僅得到巴、蜀二郡相比，顯然要實惠得多。項羽同意項伯的意見，將漢中之地又加封給劉邦，這是項羽分封中的一大敗筆。
當項王下令各受封諸王前往自己的封國時，撥給漢王3萬兵卒（漢王原有10萬兵卒，現在隻給他3萬），隨同他前往漢中。在秦末起義軍的眾將領中，漢王劉邦畢竟是一位聲望甚高、寬厚仁慈、有長者之風的人。當他前往漢中就國時，楚與各路諸侯中因仰慕而甘願隨從他前往漢中的，竟有數萬人之多。這對於漢王來說，無疑是精神上的一大安慰。
漢王率所部人馬前往漢中就國，所經由的路線是從杜縣南（今陝西西安市東南），進入蝕中（穀道名，在今陝西西安市西南）。一是可向南直通往漢中的重要穀道子午穀，南端的穀口是漢中的南康縣；一是可以向西到達眉縣西南，走斜穀，再入褒穀（斜穀與褒穀為關中通往漢中的同一條穀道的北、南二段）。從《史記·留侯世家》“良送至褒中”的記載來看，漢王是從杜縣南，經蝕中，然後西行到達眉縣，由眉縣西入斜穀，經斜穀由關中到達漢中。
在進入斜穀之前，漢王所率領的將士們一路西行。途中，這些來自東土的士卒，仰望南麵那橫亙東西的秦嶺，遠方那層巒疊翠、聳入雲端的高山，聽說山巒的那邊便是漢中，心中頓生迷茫之感，真不知自己所要奔往的去處，會是怎樣的一個世界。不用說，在這一段西行的路上，將士們的心情是低沉的，人人少言寡語。
到達眉縣西南，大軍進入斜穀。斜穀道路狹窄，幾萬大軍一字穿行於峽穀之中，蜿蜒有10餘裏之長。自進入斜穀，穿越秦嶺，又是一番景象。腳踏穀底的碎石，兩側是令人望而生畏的懸崖峭壁，飛鳥哀鳴，猿猴啼叫，亦是一片淒涼的氣氛。唯有頭頂上的那一線天空，它既給士卒們以希望，又有幾分令人恐懼，但終歸還是覺得自己的生路，隻能係在這一線天空的前方。途中，有時要行進在峭岩陡壁的棧道（又稱閣道）之上。這種棧道是峭岩陡壁上的險絕之處，傍山岩鑿出洞孔，施架橫木，鋪上木板，以通行人馬，而棧道下麵則是萬丈深淵。第一次走上這種棧道的士兵，他們一般不敢往棧道下邊觀看。即或如此，也難免膽戰心寒。
至於漢王劉邦，一路上也是思緒萬千。他總是用蕭何的勸諫，來驅散時時襲來的無名煩惱；又幸虧有張良等人一路陪同，或談笑風生；或傾聽張良講述兵法，談古論今。在部下將士們看來，他們的漢王如此神態自若，正是他們的安危和希望所在。
張良一路陪伴漢王劉邦到達褒中（今陝西勉縣東北），人馬已將要走出褒穀。此時張良以沉重的心情向漢王告辭，因為張良原是韓國的丞相，自從離開韓王輔佐劉邦入關，至此已整整一年。漢王讓張良返回韓國，張良對漢王說：“大王為何不將所經過的棧道燒毀斷絕，向天下表示沒有返還關中東向山東的意圖，用來穩定項王的心。”
臨行時，張良拉著劉邦和蕭何的手說：“你們感到日後要想統一天下，軍營裏，還缺少什麼？”
劉邦沉思片刻搖搖頭：“營之中不缺什麼，文有你及蕭何，武有曹參、樊噲和周勃，糧草馬匹兵器樣樣都有。”
張良懇切地向劉邦建議要找一個文武全才的大將軍：“我雖能出謀劃策，但手無縛雞之力，不會帶兵，蕭何克有政務之才，也不會帶兵，曹參、樊噲雖勇猛過人，但隻是一介武夫，很難統領百萬兵將，況且也無人能敵過項羽，漢王日後如何與項王爭奪天下？要想奪取天下，身旁非得有一名文武全才之人佐助，方能統兵與楚爭雄，以至日後統一天下。”
“言之有理！”蕭何聽罷點頭稱是。
張良緊握住蕭何的手：“望蕭兄好好輔助漢王，日後軍中急需廣納賢才，如能覓得一二棟梁之材，便漢必滅楚有望了。”
蕭何說：“賢弟放心！我一定盡自己全力，為大王招賢納士，振興漢軍。”
張良辭別後，漢王一邊前行，一邊派人將經過的棧道燒斷。
從褒中南行數日，漢王終於從秦嶺中間的穀道中走出，呈現在他們眼前的漢中盆地，褒水、漢水是那樣的碧綠清澈，綠樹和小溪所環繞著的農家田舍，一塊塊的水田之上，早已種上了水稻的秧苗。這時。漢王和他的將士們才個個喜笑顏開。他們好奇地觀看漢中的景物，與家鄉確實是有些不大相同；但同從關中到漢中的一路行軍比較起來，將士對漢中卻是備感親切，感到自己確實是又回到了可愛的人間。
據《史記·蕭相國世家》記載：“及高祖起為沛公，何常為丞督事。”按楚國製度，縣宰稱“公”，故劉邦起兵占據沛縣，稱“沛公”，而“丞”則是各級官吏的主要助手，如郡丞、縣丞等。蕭何自跟隨劉邦起兵後，“常為丞督事”，是說他在沛公南征北戰直至兵入關中這段期間內，蕭何一直是作為沛公的主要助手，負責掌管沛公這支起義軍的一切政務，其工作是相當繁雜而艱巨的。由於當時主要是行軍作戰，蕭何所掌管的政務亦是為作戰服務，因而他在這一期間的活動和功績，史書沒留下具體的記載。
當沛公率10萬大軍首先進入關中、接受秦王子嬰投降並將軍隊開入鹹陽後，在秦王朝也已滅亡的曆史條件下，奪取全國政權已經提到以沛公為首的這一政治軍事領導集團的議事日程之上。此刻，蕭何以其遠大的政治眼光，“獨先入收秦丞相禦史律令圖書藏之”；又勸諫沛公不要感情用事，接受封號，提出了“養其民以致賢人，收用巴、蜀，還定三秦，天下可圖”的正確路線，從而顯示了蕭何作為一位政治家的才華。因而，當沛公接受項羽賜給他的漢王稱號並率大軍來到漢中就國後，所做的第一件大事便是任命蕭何為丞相。
在南鄭的漢王府，漢王劉邦步出府門，環顧四周遠方的高山，這時他才對漢中這塊盆地有所體會。幾萬大軍進入漢中，然而這狹小的漢中盆地卻不可能成為將士們的用武之地。此時他佩服蕭何在關中為他所製定的“養其民以致賢人，收用巴蜀”路線，是何等的英明而及時。這時，漢王認識到眼前的首要任務是安定秩序，發展生產，招納賢才，製定各項製度，征收賦稅，總之，是積蓄力量，養精蓄銳，準備“還定三秦”。而這個中心任務，主要落在蕭何的肩上。
蕭何在秦時任沛縣主吏，早已顯示出不平凡的才華，因而當時泗水郡的郡監想要把他推薦到朝廷做官，但被蕭何推辭。經過幾年的戰爭風雨，特別是在鹹陽收繳了秦王朝的檔案文書之後，對於如何治理好漢中，“養其民以致賢人，收用巴蜀”，蕭何早已有所考慮，成竹在胸。至於蕭何到漢中後在丞相職務上都製定了哪些製度，做了哪些工作，史書沒有留下具體的記載，但不外乎他在關中時所談到的三個方麵：
一是“養其民”，在關中及巴蜀地區安定秩序，發展生產，積蓄力量；
二是“收用巴蜀”，派官員到巴、蜀二郡安定秩序，發展生產，征收巴蜀二郡的賦稅作為軍資，從巴蜀征召士卒以補充兵員；
三是“致賢人”，為漢王發現和推薦人才。在這方麵，蕭何所做出的巨大貢獻是向漢王推薦韓信，建議拜韓信為統兵大將。