軍中一次偶然的機會，韓信結識了劉邦軍中的丞相蕭何。兩個人多次談起軍中大事，蕭何非常賞識韓信。秦朝滅亡之後，劉邦被項羽封為漢王，實際上是被項羽排擠到了漢中，從長安到達南鄭，數十位將領看劉邦失勢了，就逃走了。韓信覺得蕭何等人多次在劉邦麵前舉薦過自己，漢王都不用，估計自己是沒什麼機會了，也逃走了，打算另投明主。
蕭何聽說韓信逃走，非常著急，來不及向劉邦報告便連夜去追趕韓信。軍中有人向漢王報告：“蕭何丞相逃走了。”劉邦聽了之後十分生氣，就如同失掉了左右手一般，連續兩天都悶悶不樂。過了兩天，蕭何前來進見，劉邦又氣又喜，罵蕭何為什麼逃跑，蕭何說他不敢逃跑，隻是去追逃亡的韓信。劉邦又罵道：“那些逃走的將領多得都以十來計數了，你一個都不追，偏偏去追一個什麼韓信，真是撒謊！”
蕭何說：“那些將領都是很容易得到的人才，而像韓信這樣的人才，全國再也找不出第二個人來，漢王您如果隻想在漢中長期稱個小王，那就不必用韓信了，如果您想要爭奪天下的話，除了韓信就沒有能幫您謀劃這件事的人了。您自己要作什麼樣的決定呢？”劉邦表示自己也想向東發展，決非甘居漢中，定要取天下。蕭何說：“漢王您既然是立誌向東發展以圖霸業，如果能對韓信委以重任，韓信就能留下；如果不能委以重任，韓信最終還是會逃跑的。”劉邦看在蕭何的情麵上同意讓韓信為將，但蕭何堅持一定要再加以重用，終於，劉邦表示可以讓他做大將軍。
劉邦想把韓信隨便召來任命他，試試他的能力，不行撤換也不遲。可蕭何說：“漢王既然已經決意要拜他為將了。就要選擇一個良辰吉日，事前齋戒，到時候要設一個祭台，所有的禮儀都應該齊備，才可以。”經過蕭何的一番勸說，劉邦最終同意了蕭何的要求。
諸將聽說漢王要拜將了，都很高興，人人都覺得自已有機會被選拜為大將軍了。等到了拜大將軍的時候，沒想到被拜將的人竟然是那個名不見經傳的韓信，全軍都感到十分驚訝。韓信拜將後，劉邦問韓信有什麼定國安邦的良策。韓信問：“同您東向而爭天下的不是項羽嗎？那大王自己估計一下，論兵力的英勇、強悍、精良，同項羽比誰高誰下？”劉邦沉默了很久後說，自己不如項王。
韓信聽後，對劉邦深深鞠了一個躬，讚同地說：“不僅大王，就連我也覺得您不如項王。可是我曾經侍奉過項王，請讓我談談項王的為人。項王隻要一聲怒喝，人人都會嚇得膽戰心驚，可是他不能放手任用賢將，所以他也就隻能算是匹夫之勇。項王待人恭敬慈愛，語言溫和，別人有疾病，他會同情落淚，把自己的飲食分給他們。可是等到部下有功應當封爵時，他把官印的棱角都磨光滑了也舍不得給人家封官，這是婦人之仁。項王雖然獨霸天下而使諸侯稱臣，可是卻不居關中而都彭城，又違背義帝的約定，把自己的親信和偏愛的人封為王，諸侯對此忿忿不平。”
韓信接著說：“諸侯見項王驅逐義帝於江南，也都回去驅逐他們原來的君王而自立為王了。凡是項羽軍隊經過的地方，無不遭蹂躪殘害，所以天下人怨恨他，百姓隻是在他的淫威下勉強屈服。名義上雖為天下的領袖，實質上已失去民心，所以他的強大會很快變成衰弱的！現在大王如能反其道而行之，任用天下勇武之人，何愁敵人不被誅滅！把天下的土地分封給功臣，何愁他們不臣服！率領英勇的一心想打回老家去的士兵，何愁敵人不被打散！”
韓信又說：“況且三秦的封王章邯、董翳、司馬欣本為秦將，率領秦國弟子已有數年，戰死和逃亡的人不計其數，又欺騙他們的部下和將領投降了項羽，至新安，項羽用欺詐的手段坑殺秦降卒２０餘萬人，唯獨章邯、董翳、司馬欣得脫，秦人對這三人恨之入骨。現在項羽以武力強封這三人為王，秦國百姓都不擁戴他們。您入關時，秋毫無犯，廢除秦國的殘酷刑法，與秦國百姓約法三章，他們無不想擁戴您在關中為王。根據當初與諸侯的約定，大王理當在關中稱王，關中的百姓都知道這件事。可大王失掉應有的封爵被安排在漢中做王，秦國百姓因而怨恨項王。現在大王起兵向東，凡屬三秦的領地，隻要號令一聲即可收服。”
劉邦聽後大喜，覺得與韓信相見恨晚。於是他對韓信言聽計從，部署諸將準備向東出擊。韓信的這番議論，實際上為劉邦製訂了以東征來奪取天下的方略。