等到項梁率領抗秦義軍渡過淮河向西進軍時，韓信帶著寶劍去投奔項梁，留在項梁的部下，一直默默無聞。項梁失敗後，韓信又改歸項羽，項羽派他做郎中。他好幾次向項羽獻計獻策，都沒有被采納。劉邦率軍進入蜀地時，韓信脫離楚軍去投奔劉邦，當了一名接待來客的小官。
有一次韓信犯了案，被判死刑，和他同案的十三個人都被殺掉了，輪到殺他的時候，他抬起頭來，正好看到劉邦手下的大將夏侯嬰，韓信就高聲說：“漢王不打算得天下了嗎？為什麽要殺掉壯士？”夏侯嬰聽他出口不凡，又見他形貌威武，就命令把他釋放了。夏侯嬰同他交談了一陣，更加佩服得不得了，便把他推薦給漢王劉邦。劉邦就派韓信做管理糧餉的治粟都尉，但還是沒覺得他是個奇才。
韓信曾多次和蕭何談天，蕭何也很佩服他。當時，劉邦被項羽趕到偏遠的巴蜀之地。劉邦的部下多半是函穀關以東的人，他們都想回到故鄉去，因此隊伍到達南鄭時，半路上跑掉的軍官就有幾十個。韓信料想蕭何他們已經在劉邦麵前多次保薦過自己，可是劉邦一直不重用自己，就也逃跑了。蕭何聽說韓信逃跑了，來不及把此事報告劉邦，就連夜去追趕。有個不明底細的人報告劉邦說：“丞相蕭何逃跑了。”劉邦極為生氣，就像失掉了左右手似的。
隔了一兩天，蕭何回來見劉邦，劉邦又是生氣，又是高興，罵道：“你逃跑，是為什麽？”蕭何答道：“我不敢逃跑，我是追逃跑的人。”“你去追回來的是誰？”蕭何說：“韓信啊！”劉邦又罵道：“軍官跑掉的有好幾十，你都沒有追，倒是去追韓信，分明是撒謊！”蕭何說：“那些軍官是容易得的，可像韓信這樣的人才，普天之下也找不出第二個來。”
就這樣，在蕭何的極力推薦下，劉邦勉強答應拜韓信為大將。劉邦手下的軍官們聽說軍中要有一位大將了，個個暗自高興，都以為被任命的會是自己。等到舉行儀式時，才知道原來是毫不起眼的韓信，全軍上下都大吃一驚。