投奔义军
陈胜、吴广起义后，项梁也渡过淮河北上，韩信此时带着宝剑投奔了项梁，留在部队，默默无闻。项梁败死后，又归属项羽，项羽让他做郎中。韩信多次给项羽献计，项羽不予采纳。刘邦入蜀后，韩信离楚归汉，做管理仓库的小官，依然不被人所知。后来韩信坐法当斩，同案的十三人都已处斩，就要轮到韩信了，韩信举目仰视，看到了滕公夏侯婴，说：“上不欲就天下乎?何为斩壮士!”(《史记·淮阴侯列传》)夏侯婴觉得此人话语不同凡响，看他相貌威武，就放了他，同他交谈，很欣赏他，于是进言汉王。汉王让封韩信一个管理粮饷的官职，没有发现他与众不同的地方。
结缘萧何
韩信多次同萧何交谈，萧何也十分赏识他。刘邦被项羽封为汉王(实为排挤到汉中)，从长安到达南郑，就有数十位将领逃亡。韩信估计萧何等人多次在刘邦面前举荐过自己而汉王不用，也逃走了。萧何听说韩信逃走，来不及向刘邦报告便去追赶韩信。军中有人向汉王报告“丞相何亡。”(《史记·淮阴侯列传》)刘邦大怒，如失左右手。过了一两天，萧何前来进见，刘邦且怒且喜，骂到萧何为何逃跑，萧何说他不敢逃跑，他只是去追逃亡的韩信。刘邦又骂到“诸将亡者以十数，公无所追;追信，诈也。”萧何说：“诸将易得耳。至如信者，国士无双。王必欲长王汉中，无所事信;必欲争天下，非信无所与计事者。顾王策安所决耳。”(《史记·淮阴侯列传》)刘邦表示自己也想向东发展，绝非甘居汉中，定要取天下。萧何说：“王计必欲东，能用信，信即留;不能用，信终亡耳。”(《史记·淮阴侯列传》)刘邦看在萧何的情面上同意让韩信为将，但萧何坚持要再加以重用，刘邦表示可以让他做为大将。于是刘邦想把韩信召来任命他。萧何说：“王素慢无礼，今拜大将如呼小儿耳，此乃信所以去也。王必欲拜之，择良日，斋戒，设坛场，具礼，乃可耳。”(《史记·淮阴侯列传》)刘邦同意了萧何的要求。诸将听说后，都很高兴，人人觉得有机会被选拜大将了。等到拜大将时，竟是韩信，全军皆感惊讶。
