原来审食其跟随着太公、吕后抄小路走，也在寻找刘邦，却偏偏碰上了楚军。楚军就带着他们回来向项羽报告。项羽一直把他们留置在军中当作人质。
这时候，吕后的哥哥周吕侯为刘邦带兵驻守下邑，刘邦顺小路去投奔他，渐渐地收集汉军士卒。驻扎在砀县。然后率军向西，经过梁地，到达虞县。
当时在下邑时，刘邦下马倚着马鞍问张良：“我打算舍弃函谷关以东等一些地方作为封赏，谁能够同我一起建功立业呢？”
张良进言说：“九江王黥布是楚国的猛将，同项羽有隔阂；彭越与齐王田荣在梁地反楚。这两个人可立即利用。您的将领中唯有韩信可以托付大事，独当一面。如果要舍弃这些地方，就把它们送给这三个人，那么楚国就可以打败了。”
张良的一番话引起了刘邦的思考。
淮南之行
五月，刘邦屯兵荥阳，各路败军都已会集在这里，萧何也把关中没有载入兵役名册的老弱人丁全部都带到荥阳，这时韩信也带着大部队来此回合，汉军重又大振。
楚军从彭城出发，一路上经常借着胜利的威势追击败逃的汉兵。可是在荥阳南面的京邑、索邑之间与汉军打了一仗，汉军打败了楚军，楚军因此不能越过荥阳向西推进。
在荥阳与楚军对峙的刘邦，此刻正焦虑地等待着随何那边的消息。
到虞县时，刘邦就对身边这帮亲近的人说：“像你们这些人，根本不配共谋大事。”在一旁负责传达禀报的随何听了，弱弱地问：“小的愚钝，陛下您能把话再说得明白些吗？”
“蠢材！”刘邦骂了一句，“谁要是能替我出使淮南，让他们发动军队，背叛楚国，在齐国把项羽牵住几个月，那我夺取天下就万无一失了。”
“小的愿替您去。”随何目光炯炯。
于是刘邦就给了他二十人一同出使淮南。
驻扎在淮南的，正是九江王黥布。
早先推翻秦朝那会儿，黥布以少胜多，打过几次漂亮的战役，是和项羽同生死共患难的铁杆战友。
当初项羽带着军队向西到达新安，趁夜袭击并活埋了章邯部下二十多万人，实际执行者就有黥布的份儿；等到了函谷关，刘邦不给开城门，也是黥布一马当先，率小队人马从隐蔽的小道入内，打败了守关的军队，才得以进关，一直到达咸阳；甚至在暗杀楚义帝事件中，黥布也扮演着重要的角色。
本来两人感情不错，却因为后来黥布两次没有派部队助战而产生了隔阂。一次是齐王田荣造反，项羽前往攻打齐国，向他征调军队，黥布托辞病重不能前往，只派几千人应征；刘邦进攻彭城，他又托辞病重不去帮忙。
项羽本来就小心眼儿，因此每回想起这事就派使者过去教训他，并召他来自己身边。黥布着了慌，生怕项羽也用对付楚义帝的那套来对付自己，所以不敢前往。
北方的齐国、赵国一直不老实，西边刘邦也起兵反楚，在项羽看来，知交的只有黥布一个，况且还需借助他的力量来对付这些不安分的家伙，所以一直没动他。
这些情况早被张良摸透，因此才会建议刘邦去争取黥布。好在多数时候刘邦都比较听话，所以才会有后来的基业；对比刘邦，项羽则变成了彻头彻尾的反面教材。
随何到了淮南后，因为太宰作内主，等了三天也没能见到黥布，于是就趁机游说太宰：“大王不召见我，一定认为楚国强大，汉国弱小，这正是我出使的原因。假使我得以召见，我的话要是说的对呢，那正是大王想听的；要是说的不对呢，就让我们一行人躺在砧板上，在淮南广场用斧头剁死好了，以此来表明大王背叛汉国亲近楚国之心。”
这番话与其说是劝告，不如说是威胁更准确。在整个形势还未明朗之际，随何逼太宰表态，不管怎么说风险都是极大的，况且人家想游说的又不是自己，何苦找麻烦呢？所以这才把话转告黥布，由此随何得以面见九江王。
随何说：“刘邦派我恭敬地上书大王驾前，我私下感到奇怪的是，大王为什么和楚国那么亲近？”
黥布说：“我面向北边以臣子的身份侍奉他。”
随何开始揭人家的短：“大王和项羽都列为诸侯，北向而以臣子的身份侍奉他，一定是认为楚国强大，可以把国家托付给他。项羽攻打齐国时，他亲自背负着筑墙的工具，身先士卒，大王应当出动淮南全部人马，亲自率领着他们，做楚军的前锋，如今只派四千人去帮助楚国。面北而侍奉人家的臣子，本来是这个样子吗？
刘邦在彭城作战，项羽还未曾出兵齐国，大王就应该调动淮南所有的人马，渡过淮河，帮助项羽与刘邦日夜会战于彭城之下。大王拥有万人之众，却没有一个人渡过淮河，这是垂衣拱手地观看他们谁胜谁败。把国家托付给人家的人，本来就是这个样子吗？
大王挂着归向楚国的空名，却想扎扎实实地依靠自己，我私下认为大王这样做是不可取的。可是，大王不背弃楚国，是认为汉国弱小。楚国的军队即使强大，却背负着天下不义的名声，因为他背弃盟约而又杀害义帝。
可是楚王凭借着战争的胜利自认为强大，刘邦收拢诸侯之后，回师驻守城皋、荥阳，从蜀、汉运来粮食，深挖壕沟，高筑壁垒，分兵把守着边境要塞。楚国要想撤回军队，中间有梁国相隔，深入敌人国土八九百里，想打，那么又打不赢，攻城又攻不下，老弱残兵辗转运粮千里之外；等到楚国军队到达荥阳、成皋，刘邦的军队却坚守不动，进攻又攻不破，退却又逃不出汉军的追击。
所以说楚国的军队是不足以依靠的。假使楚军战胜了汉军，那么诸侯们自身危惧，必然要相互救援。一旦楚国强大，恰好会招来天下军队的攻击。所以楚国比不上汉国，那形势是显而易见的。
如今大王不和万无一失的汉国友好，却自身托付于危在旦夕的楚国，我私下替大王感到疑惑。我不认为淮南的军队足够用来灭亡楚国。只要大王出兵背叛楚国，项羽一定会被牵制，只要牵制几个月，刘邦夺取天下就可以万无一失了。
我请求给大王提着宝剑归附汉国，刘邦一定会分割土地封赐大王，又何况还有这淮南，淮南必定为大王所有啊。因此，刘邦严肃地派出使臣，进献不成熟的计策，希望大王认真地考虑。”
随何的这一番话正说在黥布的心坎上，于是暗中答应叛楚归汉，没敢泄露这个秘密。
这时，楚国的使者也在淮南，正迫不及待地催促黥布出兵，住在宾馆里。随何径直闯进去，坐在楚国使者的上席，说：“九江王已归附刘邦，楚国凭什么让他出兵？”
黥布显出吃惊的样子。楚国使者站起来要走。随何趁机劝黥布说：“大事已成，就可以杀死楚国的使者，不能让他回去，我们赶快向汉靠拢，协同作战。”
到这份上，黥布也无路可选了。于是杀掉使者，出兵攻打楚国。楚国便派项声、龙且进攻淮南，项羽留下来进攻下邑。
得了消息的刘邦真是喜出望外。就在龙且的主力楚军与黥布大战的时候，刘邦乘着楚军不能分兵的空挡，赶紧兵出雍地，进袭废丘——章邯的老巢。
废丘的水仗
先前平定三秦时，章邯逃回了都城。在雎水战役时，这个前秦的老将是一箭未发就投降了项羽。他投降就算了吧，还带着他的人反戈冲乱了整个汉军联军的阵线。使得六十万大军瞬间崩溃的最大的罪人就是这个章邯。现在刘邦出来了，他要第一个废掉这个背信弃义的章邯。大军二十万，在大将郦商的率领下，向废丘出击。
这个时节正是盛夏，天气异常闷热。废丘地区又已经连续三十天没有下过雨了。环绕废丘的狼宁河都已经干涸地见底了。废丘的军民现在是吃水也感到很困难。刘邦的大军，在张良的参谋下，在郦商的率领和刘邦本人的亲自督导下，用强行军的速度向废丘进发。
而在大队来到废丘之前，郦商已经派遣了一千轻骑，携带大量的麻布口袋和铁铲等物在狼宁河上游准备拦截河水。
废丘的守卫士兵其实是看见他们的动向，也明白他们想干什么的。但是，他们想，我们现在就是河水也没有。河床都是干涸的。你的麻袋拿去可以干什么啊？拦空气啊！他们也就懒得报告将军。
将军都不知道，雍王章邯也就更加无从知道了。用了一个整整一个晚上的时间，那一千轻骑把一条狼宁河给堵塞得水泻不通。
刘邦的后续部队没有经过废丘的外围，而是绕道直接去了废丘附近，狼宁河旁边的一座小山丘。这山丘上也有雍王的小股了望部队，他们是负责只要发现敌情就立刻用烽火报警的人马。当然，也就没有派多少人了。大约也就是相当于现在一个排的兵力。
郦商在探马探知了这股敌人的存在后没有再让部队继续前进了。而是派出一百精壮的士兵，挑着好水、好酒和菜蔬，装扮成贩子，唱着秦腔就去了那小山丘。那些负责了望的官兵看见了酒水菜蔬，一个个简直是喉咙里也要伸出爪子来了。他们纷纷凑份子，买了一桶酒，要了一桶水，还买了写下酒菜，慢慢地品酌起来。而那些贩子依旧唱着秦腔，慢悠悠从山秋那边下去了。
在半个时辰后，那些守卫的士兵就不会再动弹了。他们被药麻翻了。在他们清醒过来前，嘴巴就被堵了个严实，手脚也被捆绑起来。刘邦的大军立即把个山丘驻扎得满满当当的，连个插针的地界也没有了。
就在刘邦大军秘密抵达废丘的当天晚黑，狼宁河的上游是阴云密布，转眼间便是雷霆万钧，再接着就雨箭乱射。狼宁河的河水顿时暴涨起来。而这次下雨在废丘却没有丝毫雨意，那里的天气还是那样闷热。那些熟睡的雍王士兵根本不知道他们已经在面临一场大难了。
就在这些士兵熟睡的时候，负责看护上游独水的人马接到抽开麻袋的指令。大水，已经憋坏了的大水向亿万头的野狼，发疯似地向废丘冲去。也就在河水即将抵达废丘的瞬间。在山丘上的士兵，迅速地把他们手里的麻袋堵住了狼宁河的下游。在河水疯狂地冲到下游的时候，它们发现河道已经没有了。本来已经发怒的河水是更加地暴怒起来。他们在发怒的间隙，猛可间发现旁边还有一条捷径。喜滋滋的大水顿时往废丘城冲去。废丘，在就是片刻间成为一片汪洋……
废丘城头升起一片白色降幡。这水本来就是阵雨的结果，是来得快，去得也快。大水很快退去。刘邦现在又一次面对再次要投降的章邯。而章邯虽然下令部队投降了，他自己却是依然笔立着，没有丝毫要过来见刘邦的意思。只见章邯，全身上下白盔白甲、一袭雪白的战裙，加上花白的胡须。他一手持长枪、一手横握宝剑，只见他对天大笑几声：“先帝啊，微臣追随你来了。”就看见章邯斗大的人头骨碌碌地向前滚动了十多步，而章邯的身躯在夏天炎热的夜空下却坚持没有倒下。他的手扶着长枪，一个无头将军，象铁铸的象，虽然是有点歪斜，却还是屹立着、屹立着……
刘邦终于明白了这个三番五次投降的秦将的心意了，他是想利用诸侯的仇隙来达到他重建大秦王朝的目的。这真是一个坚韧、忠勇的将军啊！刘邦对着章邯的尸体连续地鞠了九次躬，又说将来建立汉朝后一定要让秦地繁荣，不让血液继续因为战争为白流。然后，在刘邦的号令下，汉均二十万集体向章邯的尸身鞠躬。在过了又是半个时辰后，那铁铸的无头将军才轰然地倒地了。坚实的城墙上也给砸出一个深深的坑凼。
废丘被攻下了，刘邦把这个地方更名为槐里。然后命令在这里设置官府和留置官员。以便在四时可以祭祀苍天、河川和死难的英灵。在办完这一切后，刘邦的大军又向前开拔而去。
黥布这边跟龙且的大部队僵持了几个月，拖住楚军主力部队的任务也算完成了，于是就想带兵撤退到汉国。可又怕楚国的军队拦截杀掉他，所以，就和随何从隐蔽的小道逃归汉国。
黥布到时，刘邦正坐在床上洗脚，就叫黥布去见他。黥布见状，怒火燃胸，后悔前来，想要自杀。当他退出来，来到为他准备的宾馆，见到帐幔、用器、饮食、侍从官员一如刘邦那么豪华，黥布又喜出望外。于是就派人进入九江。
这时楚王已经派项伯收编了九江的部队，杀尽了黥布的妻子儿女。黥布派去的人找到当时的宠臣故友，带着几千人马回到汉国。刘邦又给黥布增加了兵力一道北上，到成皋招兵买马。汉四年七月，刘邦封黥布为淮南王，共同攻打项羽。
虽然被项羽追得满世界跑，可刘邦还是抽出时间来搞宣传。“关中王”的名号已经叫了很久，自己还没立王储呢！于是在这一年的六月立孝惠为太子，大赦罪犯。让太子守卫栎阳，把在吴中的各诸侯的儿子也都集中到栎阳来守卫。