虽然愿意跟随刘邦进汉中的人很多，但是前往汉中的道路（栈道）实在难走。栈道的底下是千丈深谷，一不小心掉下去便立刻粉身碎骨。有些特别艰险的地方只容得下一个人单独小心通过，所有的粮食、器具、武器都必须用人力背过去。所有行人只能沿着山路逐步攀爬前进，那些体力不济或过分粗心的人，往往不知不觉地葬身在千丈的云雾谷底中。
在行军途中，不慎失足而死的人愈来愈多，军中充满了悲情气氛。一些兵士纷纷打退堂鼓，不辞而别地从原路逃了回去。
大家好不容易到了南郑，总算可以安顿下来松口气了，但是，这里的条件不如关中，更不如中原地区，吃的、住的、穿的、用的都很不习惯，条件非常艰苦。刘邦的部众大多是关东人，见汉中的条件如此差，一个个都后悔起来，不少士兵继续逃亡，甚至有不少部将也离开了。
对于官兵们开小差，刘邦一时束手无策，不知道怎么办才好，便顺其自然。他显得满不在乎，既不追捕逃亡者，也不追究监守者的责任，一副要走请自便的样子。虽然这种自信是装出来的，但是他也意识到民心是最重要的，强迫将士们留下，对自己将来的发展并没有什么好处。
不过，刘邦的心理素质再好，也有沉不住气的时候。一天早上，有人前来向刘邦报告：“丞相萧何昨晚私自离去。”
刘邦一听，犹如五雷轰顶，又气又急：“怎么可能，连萧何都逃亡了，我还能依靠谁呢？”萧何是跟随刘邦从沛县起兵的骨干分子，是刘邦阵营中的骨干人员，堪称刘邦的左右手。失去了左右手，那还得了，刘邦几乎要崩溃了。
好在没几天萧何又回来了，并立刻向刘邦报到。刘邦又气又高兴，见了面，马上就问萧何干什么去了。萧何说自己追韩信去了。
原来，韩信知道萧何已在刘邦面前数度提起和推荐过自己，但刘邦总是不为所动。韩信心想，像萧何这种备受刘邦器重的重量级人物都推举无效，其他人就更不用指望了，或许刘邦根本就不需要像自己这样的人才。如果确实是如此，那么自己留下来还有什么意思呢？于是，韩信决定逃回中原，另外寻找出人头地的机会。
萧何得到韩信逃走的消息非常震惊，来不及告诉刘邦就骑马追了出去。追赶了两天，萧何终于在快出汉中的边界将韩信追了回来。这就是历史上流传的“萧何月下追韩信”的典故。
刘邦见萧何回来，悬在心里的石头终于落地了，但他始终无法理解萧何为什么那么看重韩信，他甚至有些赌气地对萧何说：“诸将亡者以十数，公无所追；追信，诈也。”意思是说：我手下的重要将领逃亡了几十人，你一个也不去给我追回来，你说你去追韩信，你骗谁呀！
萧何回答说：“我之所以不追那些逃亡的将领，是因为他们只是普通的将才，这样的人多的是，到哪里都能抓一把，至于像韩信这种人才，普天之下没有第二个，绝对不能让他离开。当然，如果大王只想长期在汉中当王，那么韩信可能派不上什么用场，但是如果大王真的要想夺取天下，那么没有韩信肯定不行。现在韩信我已经帮您追回来了，但是能不能留住韩信，那就要看大王是想安心在汉中做个王呢，还是做一个天下共主的真命天子？何去何从，全凭大王您自己决断。”
刘邦一听，立即说：“我当然想挥师东进与项羽争夺天下，怎么可能一辈子呆在汉中这个鬼地方呢？”
萧何说：“大王即使有如此远大的志向，也未必能留住韩信，除非您重用他，他才会留下来；否则，如果您不重用他，您纵然有天大的志向，他也会再次逃去的！”言下之意，如果韩信再度逃去，恐怕谁也追不回来了。
刘邦见萧何把话说到了这个份儿上，知道不重用韩信不行了，于是便问萧何该给韩信安排个什么官做。
萧何回答说：“如果只给他安排一个普通将领的职位，那是肯定留不住他的，要想让他留下来，就必须安排他做大将。”
“好，那就封他为大将。”刘邦很爽快地答应了，并立即命人草拟文书，准备下达任命，封韩信为大将。
萧何见刘邦一反常态，这样轻松地封大将，简直是视封大将如同儿戏，心里很不高兴，他表情严肃，十分郑重地对刘邦说：“大王必须选择一个良辰吉日，斋戒筑坛，正式拜封韩信为大将。”
刘邦见萧何如此认真，不依不饶，只好满口答应。
于是，刘邦传下令去，命人筑起高台，选择良辰吉日，准备斋戒后登台拜将。
消息一传开，那些跟随刘邦起兵、出生入死的重要将领如樊哙、曹参、周勃等都暗自高兴，他们以为凭着自己和刘邦的交情，凭着自己几年来为刘邦立下的汗马功劳，大将一职非自己莫属。但是等到拜将的那一天，当刘邦宣布韩信为大将军，并让他上台领受将印时，不仅他们感到吃惊，而且几乎所有的将士都感到非常意外。当然，最不服气的要数樊哙，他仗着自己是刘邦的连襟（北方话叫“担挑”），并在鸿门宴上护驾有功，当场大闹了一番。不过在刘邦的厉声喝斥下，他也只好黯然退场，事后又不得不去韩信那里道歉。其实，这个樊哙是性情中人，此时韩信的名声不好，钻过别人的裤裆，很少有人看得起他，樊哙也不例外。等到他后来领略了韩信的神奇用兵方略后，又立即对韩信佩服得五体投地，刘邦统一天下后，即使韩信从楚王被贬为了淮阴侯，他也一样用对待“王”的礼节对待他。这是后话。
不管怎么说，一个平时不为人知的军中小官，如今一下子被拜为大将，凌驾于众多资历和战功都很显赫的重要将领之上，肯定会有很多人不服。刘邦意识到了这一点，于是晓谕众将：凡我将士，今后俱由大将军韩信节制，大将军当善体寡人之意，与士卒同甘共苦，除暴安良，匡扶王业。从现在起，有藐视大将军、违令不从者，准以军法从事，先斩后奏！
韩信拜将以后，刘邦对他礼遇有嘉，众将见刘邦如此厚待韩信，也不敢对韩信不恭。一天，刘邦把韩信请入帐中，让他坐在上宾的位置，郑重地对他说：“丞相多次向我推荐将军，称赞将军的雄才大略，如今我想挥师东进，将军会用什么方略来指教我呢？”
韩信起身致歉，没有直接回答他的问题，而是反问道：“如今大王向东去争夺天下，对手难道不是项王吗？”
刘邦回答说：“是的，正是项王。”
韩信又问：“既然如此，大王试想一想，您在勇悍强仁方面和项王相比怎么样？”
汉王沉默良久，回答说：“在这几个方面，我都不如项王。”韩信听了刘邦的话，感觉刘邦还算是个敢于面对现实、承认差距、有自知之明的人，于是心里有了底。他向刘邦拜了两拜，说：“臣也认为大王在这几方面不如项王。不过，这不足为忧，且听我细细道来。臣曾经以郎中的身份侍奉过项王，对于他的为人比较了解。他的刚烈威猛无人能敌，打起仗来大喝一声，能使数以干计的敌人胆战心惊，所以，他能驰骋于乱军之中斩将夺旗，如入无人之境。但也正是因为如此，导致他太刚愎自用，不能任用有才能的将领，由此看来，他的所谓刚烈勇猛不过是逞匹夫之勇罢了（是一个勇敢的战士，而不是一个好的军事统帅）。从表面上看，项王待人仁慈有礼，言语温和，比如部下有人生了病，他总会去问长问短，把自己的饮食分给他们吃，如果部将病死了，他会悲痛流泪，可是当他的部下立了战功应该赐爵封位时，他却把刻好的印章拿在手里反复把玩，印章的棱角都磨得差不多了，也舍不得给人家，可见他所谓的仁义也不过是妇人之仁而已。项王虽然称霸天下，臣服诸侯，可是他不思占据具有战略地位的关中，却定都于无险可守的彭城，这显然是自失地利。况且他违背义帝的约定，以亲疏关系为分封诸侯的依据，擅自分封，该封的他不封，不该封的他却乱封，把自己喜欢和亲近的人都分封为王，因此，很多诸侯都对他心存不满。对他更不利的是，他违背道义，擅自迁徙和驱逐‘义帝’，把他安置在江南，不少诸侯都看在眼里，并且起而效尤。试看山东诸国，已有不少背信弃义之徒开始驱逐旧主，占据富饶肥沃之地，自立为王，天下又一次陷入了动荡不安的境地。最致命的是项王军队虽然很多，但纪律非常不好，自从他起兵以来，攻州掠郡，所到之处无不大肆杀戮，甚至坑杀降卒，早已失去了民心，老百姓根本就不向着他，目前之所以敢怒不敢言，只是慑于他的威势而已。因此，从名义上看项王虽然是天下霸主，但是他已失去了天下人心，虽然他勇敢善战，但部下不支持他，诸侯与他离心离德，更得不到老百姓的拥护，所以，他所谓的强大其实很容易被弱化。”
韩信对项羽的人品和为人处世的特点进行了一番分析后，进一步向刘邦指出，只要应对方法得当，项羽是不难战胜的。他继续对刘邦说：“大王应该针对项羽的为人和处事方法，反其道而行之，任用天下能征善战之士，让他们充分施展才能，给他们广泛提供建功立业的机会，这样一来，有什么样的敌人不能被诛灭呢？只要大王能厚待有功将士，把天下的城池都封赏给他们，不要像顼羽那样吝啬，这样所有的将士都会感激和佩服大王，听从您的指挥，为您奔走效命，这样一来，普天之下，还有谁敢不服大王呢？大王起自丰沛，率领将士辗转向西攻秦，如今强秦已灭，项王却将大王分封到偏远的汉中，将士们大多是崤山以东的人，他们日夜思念故土，想早点打回老家去，大王若能顺从将士之意，传檄天下，列数项王的种种罪行，率领正义之师挥戈东进，将士们必然万众一心，众志成城，这样一来，还有什么样的敌人不会被望风瓦解呢？况且三秦之地现在由章邯、司马欣、董翳据守，这三人原是秦朝的将领，率领秦军镇压起义军，所杀不计其数，一方面原有的反秦势力痛恨他们；另一方面，他们被项王打败后，又欺骗部下向项王率领的诸侯联军投降，部队到达新安以后，项王用诈骗的手段活埋了20多万降卒，而章邯、司马欣和董翳却得以保全性命。这20多万人都是关中父老的子弟兵，他们认为是这三个人出卖和葬送了这些子弟兵，用他们的生命换取了自己的荣华富贵，所以对他们恨入骨髓。项王虽然凭着自己的威势封这三个人为王，分镇关中，以阻止大王东进，但是，关中地区的老百姓会帮他们吗？绝对不会。相反，先前大王进入武关之后，对百姓秋毫无犯，废除了秦朝的严刑酷法，进入咸阳后，又与老百姓约法三章，为民做主，解民于倒悬，救民于水火，关中父老奔走相告，欢呼雀跃，没有谁不希望大王能够长留关中，做他们的关中王。况且按照怀王与诸侯的约定，谁先进入咸阳、平定关中，谁就做关中王。这一点天下人都是知道的，关中百姓更是人人皆知。但是，项王入咸阳后，纵兵抢掠，焚烧宫室，大失人望，又违背怀王旨意，擅自分封诸侯，不但不如约封大王为关中王，反而把大王封到更偏远的汉中，对此，关中地区的老百姓无不痛心疾首，并日夜盼望大王早日东归。因此，现在只要大王起兵东进，关中之地可传檄而定。”
刘邦听了，茅塞顿开，连连称奇，此时他终于明白萧何为什么不打招呼就去连夜追回韩信。的确正如萧何所说，韩信这样的人是“国士无双”，要想东向与项羽争夺天下，一定少不了韩信这样的人。刘邦在兴奋之余竟有些手舞足蹈，一个劲儿地说自己有眼无珠，不识大贤。他郑重地对韩信说：“寡人深恨没有早日起用将军！今日幸蒙将军赐教，茅塞顿开。从今以后用兵打仗全仗将军指挥调度，指日东征！”
韩信见刘邦兴奋得有些过头，于是又扭转话题，转移到军队的现状上来，他说：“将不练不勇，兵不练不精。虽然项王有不少不足之处，但他毕竟是身经百战的常胜将军，千万不可小视。我们的当务之急是加紧操练人马，鼓舞斗志，大约需要一个多月的时间，方可起兵东征。”
汉王连声叫好，随即命令韩信前去部署，整顿部伍，制定军规，训练士卒。
在这次君臣对话中，韩信初试锋芒，分析了楚汉双方的利弊得失，指出了汉军必胜、楚军必败的主客观条件，并提出了东征的具体部署，使刘邦看到了希望。尤其值得一提的是，韩信在分析形势时，并不是单纯地从军事力量的对比着眼，而是把战争的胜负同人心的向背紧密联系起来，表现了超人的政治远见和卓越的军事才能。
刘邦拜将以后，韩信成了三军总司令，从此以后，他开始了叱咤风云的军事生涯。在中国历史上留下了赫赫战功，成就了中国古代第一战将的美名。
