韩信在项羽手下干，看不到前途不说，而且因为自己的名声不好，人品也被项羽看不起，这让他感到很窝火。于是整天想着要找一个能赏识自己的明主，但环视天下诸侯谁又称得上是明主呢？很快地，他发现了一个人，这个人就是那位在各路诸侯中出身最卑微的刘邦。在此，我们不妨对刘邦作个简要的介绍。
这刘邦原是投奔项梁的，本身没有什么背景，但他手下有一批能人，像萧何、曹参、樊哙、周勃、夏侯婴等都非等闲之辈，而且因为刘邦这个人本身不是出自名门望族，为人比较随和，不太看重对方的身份，只要能帮他打胜仗、对他忠心耿耿就行。所以，大家对他的评价都比较高，他在怀王集团中很有人缘，也深得项梁器重，并很快成为项梁手下一位很有分量的人物，常常和项羽并肩作战。项梁死后，怀王让宋义接替了项梁的军事指挥权。在怀王集团中，由于项家军的势力过于庞大，难以驾驭，项梁死后，怀王和宋义为了打击项羽的势力，便有意抬高刘邦的地位，借此牵制项羽。当时，秦将章邯率军攻打赵国，形势非常危急，赵王数次遣使向怀王求救。于是，怀王任命宋义为上将军、项羽为次将、范增为末将，率军北上救赵，然后再折向西攻击秦军，直逼秦都咸阳；同时，派刘邦率领本部人马直接向西攻城略地，与宋义所部形成夹钳攻势，威逼咸阳。临行前，怀王与诸将相约：“先入定关中者王之”。也就是说先进入咸阳、平定关中的人封他为关中王。
在北上途中，宋义按兵不动，静观其变。项羽则以此为借口，说他贻误军机，发动兵变，杀掉了宋义，夺取了军队的领导权，然后率部渡河，破釜沉舟，与章邯在巨鹿展开激战。由于秦军主力尽被吸引于此，刘邦便乘虚向西攻击，势入破竹，于公元前207年10月挥师直抵距咸阳不远的霸上。此时，赵高已经杀掉秦二世，拥立二世的侄儿子婴，削去帝号，称秦王。不久，子婴又杀掉赵高，打开城门向刘邦投降了。
进入咸阳后的刘邦，并没有摆出一副征服者的派头，他召集咸阳父老集会，对他们说：你们在秦朝的暴政下煎熬已久，诽谤朝政的人要被诛灭九族，相互私语的人要被杀头示众。这样的王朝怎么能不灭亡呢？怀王与诸将曾经有约，先进入关中的人就封他为关中王，如今我率先进入咸阳，平定关中，理所当然应该成为关中王。现在我与你们约法三章：“杀人者死，伤人及盗抵罪。”随后，刘邦又废除秦朝的全部法律，下令各级官吏都要忠于职守，与老百姓秋毫无犯。关中父老奔走相告，几百年来一直生活在秦氏高压和恐怖氛围中的关中百姓欢呼雀跃，衷心拥戴刘邦，刘邦很快就赢得了关中父老的认可。刘邦与关中父老约法三章后，随即还军霸上，等待诸侯军队的到来。
对于这一切，韩信都是知道的。他从中看出了刘邦的与众不同，知道他是位能成大事的人物，所以对他心仪已久。
项羽大败秦军主力，并迫使秦军主将章邯投降，威震天下，成为节制诸侯的上将军。随即他率军火速往关中进发，当他到达函谷关时，却发现关门紧闭，刘邦已率先进入关中，占领了秦都咸阳，而函谷关的守军居然不让他入关。他觉得既没面子，又很窝囊，自己九死一生、浴血奋战，却让刘邦趁虚捡了漏子。于是，他发兵攻下函谷关，准备闪击刘邦。当时，刘邦只有10万人马驻在霸上，而项羽却拥有40万能征善战的军队，驻扎在新丰鸿门。为了避免以卵击石，刘邦决定暂时屈服，亲至鸿门向项羽谢罪，逃过了一劫。这就是历史上所说的“鸿门宴”。
此时的项羽在天下诸侯中的威信达到了极点，大有“环视天下，舍我其谁”的霸气，于是，擅自做主分封诸侯。本来从道义和名分上讲，项羽虽然身为诸侯上将军，但是怀王是项羽的主子，要分封诸侯也应该由怀王来分封，然而，此时的项羽完全把怀王抛在了一边，只是出于礼节，尊他为“义帝”。这还不算，在分封诸侯时，他又违背怀王当初与诸将的约定，即“先入定关中者王之”，不但不封刘邦为关中王，反而把他封到偏远的巴、蜀、汉中地区，让他去做汉王，定都南郑。这种背信弃义的做法很让人失望，这让原先楚军集团的很多将领都对项羽有了看法。不仅如此，他对其他诸侯的分封也多有不公平的地方，尤其是对英布、彭越的分封，就让二人感到很不满意，这为二人后来转投刘邦埋下了祸根。对于齐国的实力派人物田荣，项羽更是不予承认，迫使田荣在不久之后就举兵反叛，逼走了项羽所立的齐王田都，杀死了项羽新立的胶东王（原来的齐王田市），并自立为齐王。这样一来，原本在诸侯中有着至高无上的威信的项羽就因为分封不公，一下子又成了众多诸侯的矛头所向，埋下了干戈再起的种子。
项羽则自封为西楚霸王，占据天下最富饶的九个郡，建都彭城，而把天下共主的“义帝”（即怀王）迁往长沙郴县，并密令衡山王、临江王在怀王渡江时，将其击杀于江中。
由于项羽在西进咸阳的途中坑杀了秦军20万降卒，只留下了章邯、董翳、司马欣三位降将，这些士兵都是关中父老的子弟兵，项羽此举让关中父老颇为痛心。进入咸阳后，项羽又纵兵劫掠，焚烧咸阳城，大火三月不绝，这使关中父老意识到项羽比秦始皇更加残暴，他们恨透了项羽。项羽也自知得不到关中父老的支持，无意在关中久留，于是便封章邯为雍王，定都废丘；封司马欣为塞王，定都栎阳；封董翳为翟王，定都高奴。关中地区由此被一分为三，所以又称“三秦之地”。项羽让他们分镇关中，以阻止前往汉中的刘邦东进。
刘邦接受分封后，决定前往自己的封地就国。此时的刘邦拥有10万大军，但是项羽为了限制刘邦的力量，只允许他带3万人马。不过，刘邦的亲信和部下很多，他们都愿意跟随刘邦去汉中，还有一些诸侯的部属因为敬慕刘邦的为人，也主动表示愿意跟随刘邦前往汉中，所以跟随刘邦去汉中的人远远超过了3万。而在那些敬慕刘邦、愿意跟随他前往汉中的人中就有韩信。
韩信知道在项羽麾下毫无用处，决心另寻新主，以施展自己的才华。经过一段时间的观察后，他把希望寄托在了刘邦的身上，决定追随刘邦。于是，在刘邦离开咸阳前往汉中前，韩信主动向项羽请示，愿意跟随刘邦进入汉中。项羽早就对他感到厌烦，便趁机把他划归到刘邦属下。
但是，韩信离开项羽投奔刘邦，并未很快实现他出人头地的愿望。因为当时他“未得知名”，除了他在淮阴市井那些不好的名声外，确实拿不出让人信服的名气。估计以他当时的身份来到刘邦军中时，连刘邦的面也没有见到，而由刘邦的部将比照他在项羽军中的职位，给他安排了一个很小的官职：连敖。连敖是个什么官呢？就是搞接待工作的，有点像我们现在所说的公关先生。而他之所以能当上连敖，大概还是因为他身材高大，长得挺帅，又能说会写的缘故。看来要在刘邦的军中出人头地也不是那么容易，路还长得很。怎么办呢？那就干脆干点出格的事吧，这样或许能引起刘邦的注意。
干点什么出格的事呢？在军队里，军规是最神圣的，一般人都不敢拿军规开玩笑。为了引起一些重量级人物的注意，在他不经意的策划下，一帮人和他一起糊里糊涂地便犯了军规。按规定犯了军规的人该杀头，执行军规的人不是别人，正是在沛县跟随刘邦起兵的夏侯婴，这个夏侯婴在刘邦面前也是个红人，早在刘邦做泗水亭长的时候，他就在沛县衙门里管事，已升为试补县吏，比刘邦的职位高，但是他很佩服刘邦，跟刘邦很亲近。有一次，刘邦与夏侯婴比剑玩时，一不小心把夏侯婴砍伤了，此事正好被其他县吏看到，便密告刘邦故意伤害官差。
刘邦身为亭长，却伤害朝廷官差，依照秦法不但会被革职，还要被判处重罪。由于事态严重，刘邦怎么也不承认夏侯婴是他刺伤的。县官没有办法，只好找夏侯婴，要他出面指控刘邦，夏侯婴也坚决不承认是刘邦剌伤了他。县官恼羞成怒，把案子翻了过来，以“知情不报，匿护罪犯”之罪名，将夏侯婴鞭笞了数百下，并把他打入大牢，判处一年刑狱。刘邦终于得以解脱，夏侯婴对此也无怨无悔。当然，刘邦对夏侯婴的“义举”也非常感激，他在沛县起兵后，夏侯婴追随在他的左右，深得刘邦信赖。
韩信等人犯了军规，夏侯婴亲自监斩，很快就杀掉了其他的13个人。轮到要杀他了，他抬起头来对夏侯婴说：“上不欲就天下乎？何为斩壮士！”汉王不是想得到天下吗，既然如此，为什么要这样随便斩杀自己的子弟兵呢？
夏侯婴是见过大场面的人，听了韩信的话很是诧异，觉得这个人不一般。于是就没有杀他，给他松了绑，还和他长聊。谁想不聊不知道，一聊吓一跳，原来这个韩信居然有如此过人的才能，于是他赶紧前往刘邦那里，向刘邦提起了韩信这个人。刘邦听了很感兴趣，不过人事任命非同小可，就像我们今天要提拔某个人之前，照例先要派人事部、组织部去调查一番，看这个人的群众基础怎么样。可是调查的人回来说韩信这个人以前在淮阴市井的时候，靠混饭吃过日子，而且还当众从一个地痞的裤裆下钻了过去。刘邦一听调查的人这样说，自然对韩信也不感冒了，于是只给了他一个治粟都尉的头衔，也就是押运粮草的官。
就这样，韩信当了治粟都尉，虽说这个官并不大，但却给了他结识更多重量级人物的机会，尤其是刘邦非常器重的萧何。萧何自刘邦起兵以来，一直是刘邦的后勤部长，刘邦被封为汉王后，他又封萧何做了丞相，让萧何负责治理封国，并兼管军队的后勤工作，军队的粮草供应他当然是要过问的。就这样，韩信和萧何也相识了。
一天，他和萧何谈古论今，语及兵法战略，萧何大惊，认为韩信是一块尚待琢磨的玉，是当今天下不可多得的人才，更是刘邦阵营中最缺乏的人才，身为丞相，即使他给韩信任何一个他能安排的官职，都不能让他完全发挥他的才能。因此，对于韩信，萧何想让刘邦自己来安排重用他。
不过，萧何一向较冷静，也不愿将心中的想法过早地让韩信知道，以避免韩信因为急于成功，表现得太积极，从而引起其他将领的反感。
韩信确信萧何必定深为自己的见解所折服，也确信萧何向刘邦推荐了自己，然而很多天过去了，韩信还是没有等来刘邦的召见，更不用说重用自己了。看来刘邦对自己确实有成见，并不想重用自己，于是韩信又萌生了去意。