原來審食其跟隨著太公、呂後抄小路走，也在尋找劉邦，卻偏偏碰上了楚軍。楚軍就帶著他們回來向項羽報告。項羽一直把他們留置在軍中當作人質。
這時候，呂後的哥哥周呂侯為劉邦帶兵駐守下邑，劉邦順小路去投奔他，漸漸地收集漢軍士卒。駐紮在碭縣。然後率軍向西，經過梁地，到達虞縣。
當時在下邑時，劉邦下馬倚著馬鞍問張良：「我打算捨棄函谷關以東等一些地方作為封賞，誰能夠同我一起建功立業呢？」
張良進言說：「九江王黥布是楚國的猛將，同項羽有隔閡；彭越與齊王田榮在梁地反楚。這兩個人可立即利用。您的將領中唯有韓信可以托付大事，獨當一面。如果要捨棄這些地方，就把它們送給這三個人，那麼楚國就可以打敗了。」
張良的一番話引起了劉邦的思考。
淮南之行
五月，劉邦屯兵滎陽，各路敗軍都已會集在這裡，蕭何也把關中沒有載入兵役名冊的老弱人丁全部都帶到滎陽，這時韓信也帶著大部隊來此回合，漢軍重又大振。
楚軍從彭城出發，一路上經常藉著勝利的威勢追擊敗逃的漢兵。可是在滎陽南面的京邑、索邑之間與漢軍打了一仗，漢軍打敗了楚軍，楚軍因此不能越過滎陽向西推進。
在滎陽與楚軍對峙的劉邦，此刻正焦慮地等待著隨何那邊的消息。
到虞縣時，劉邦就對身邊這幫親近的人說：「像你們這些人，根本不配共謀大事。」在一旁負責傳達稟報的隨何聽了，弱弱地問：「小的愚鈍，陛下您能把話再說得明白些嗎？」
「蠢材！」劉邦罵了一句，「誰要是能替我出使淮南，讓他們發動軍隊，背叛楚國，在齊國把項羽牽住幾個月，那我奪取天下就萬無一失了。」
「小的願替您去。」隨何目光炯炯。
於是劉邦就給了他二十人一同出使淮南。
駐紮在淮南的，正是九江王黥布。
早先推翻秦朝那會兒，黥布以少勝多，打過幾次漂亮的戰役，是和項羽同生死共患難的鐵桿戰友。
當初項羽帶著軍隊向西到達新安，趁夜襲擊並活埋了章邯部下二十多萬人，實際執行者就有黥布的份兒；等到了函谷關，劉邦不給開城門，也是黥布一馬當先，率小隊人馬從隱蔽的小道入內，打敗了守關的軍隊，才得以進關，一直到達咸陽；甚至在暗殺楚義帝事件中，黥布也扮演著重要的角色。
本來兩人感情不錯，卻因為後來黥布兩次沒有派部隊助戰而產生了隔閡。一次是齊王田榮造反，項羽前往攻打齊國，向他徵調軍隊，黥布托辭病重不能前往，只派幾千人應徵；劉邦進攻彭城，他又托辭病重不去幫忙。
項羽本來就小心眼兒，因此每回想起這事就派使者過去教訓他，並召他來自己身邊。黥布著了慌，生怕項羽也用對付楚義帝的那套來對付自己，所以不敢前往。
北方的齊國、趙國一直不老實，西邊劉邦也起兵反楚，在項羽看來，知交的只有黥佈一個，況且還需借助他的力量來對付這些不安分的傢伙，所以一直沒動他。
這些情況早被張良摸透，因此才會建議劉邦去爭取黥布。好在多數時候劉邦都比較聽話，所以才會有後來的基業；對比劉邦，項羽則變成了徹頭徹尾的反面教材。
隨何到了淮南後，因為太宰作內主，等了三天也沒能見到黥布，於是就趁機遊說太宰：「大王不召見我，一定認為楚國強大，漢國弱小，這正是我出使的原因。假使我得以召見，我的話要是說的對呢，那正是大王想聽的；要是說的不對呢，就讓我們一行人躺在砧板上，在淮南廣場用斧頭剁死好了，以此來表明大王背叛漢國親近楚國之心。」
這番話與其說是勸告，不如說是威脅更準確。在整個形勢還未明朗之際，隨何逼太宰表態，不管怎麼說風險都是極大的，況且人家想遊說的又不是自己，何苦找麻煩呢？所以這才把話轉告黥布，由此隨何得以面見九江王。
隨何說：「劉邦派我恭敬地上書大王駕前，我私下感到奇怪的是，大王為什麼和楚國那麼親近？」
黥布說：「我面向北邊以臣子的身份侍奉他。」
隨何開始揭人家的短：「大王和項羽都列為諸侯，北向而以臣子的身份侍奉他，一定是認為楚國強大，可以把國家托付給他。項羽攻打齊國時，他親自背負著築牆的工具，身先士卒，大王應當出動淮南全部人馬，親自率領著他們，做楚軍的前鋒，如今只派四千人去幫助楚國。面北而侍奉人家的臣子，本來是這個樣子嗎？
劉邦在彭城作戰，項羽還未曾出兵齊國，大王就應該調動淮南所有的人馬，渡過淮河，幫助項羽與劉邦日夜會戰於彭城之下。大王擁有萬人之眾，卻沒有一個人渡過淮河，這是垂衣拱手地觀看他們誰勝誰敗。把國家托付給人家的人，本來就是這個樣子嗎？
大王掛著歸向楚國的空名，卻想扎扎實實地依靠自己，我私下認為大王這樣做是不可取的。可是，大王不背棄楚國，是認為漢國弱小。楚國的軍隊即使強大，卻背負著天下不義的名聲，因為他背棄盟約而又殺害義帝。
可是楚王憑藉著戰爭的勝利自認為強大，劉邦收攏諸侯之後，回師駐守城皋、滎陽，從蜀、漢運來糧食，深挖壕溝，高築壁壘，分兵把守著邊境要塞。楚國要想撤回軍隊，中間有梁國相隔，深入敵人國土八九百里，想打，那麼又打不贏，攻城又攻不下，老弱殘兵輾轉運糧千里之外；等到楚國軍隊到達滎陽、成皋，劉邦的軍隊卻堅守不動，進攻又攻不破，退卻又逃不出漢軍的追擊。
所以說楚國的軍隊是不足以依靠的。假使楚軍戰勝了漢軍，那麼諸侯們自身危懼，必然要相互救援。一旦楚國強大，恰好會招來天下軍隊的攻擊。所以楚國比不上漢國，那形勢是顯而易見的。
如今大王不和萬無一失的漢國友好，卻自身托付於危在旦夕的楚國，我私下替大王感到疑惑。我不認為淮南的軍隊足夠用來滅亡楚國。只要大王出兵背叛楚國，項羽一定會被牽制，只要牽制幾個月，劉邦奪取天下就可以萬無一失了。
我請求給大王提著寶劍歸附漢國，劉邦一定會分割土地封賜大王，又何況還有這淮南，淮南必定為大王所有啊。因此，劉邦嚴肅地派出使臣，進獻不成熟的計策，希望大王認真地考慮。」
隨何的這一番話正說在黥布的心坎上，於是暗中答應叛楚歸漢，沒敢洩露這個秘密。
這時，楚國的使者也在淮南，正迫不及待地催促黥布出兵，住在賓館裡。隨何徑直闖進去，坐在楚國使者的上席，說：「九江王已歸附劉邦，楚國憑什麼讓他出兵？」
黥布顯出吃驚的樣子。楚國使者站起來要走。隨何趁機勸黥布說：「大事已成，就可以殺死楚國的使者，不能讓他回去，我們趕快向漢靠攏，協同作戰。」
到這份上，黥布也無路可選了。於是殺掉使者，出兵攻打楚國。楚國便派項聲、龍且進攻淮南，項羽留下來進攻下邑。
得了消息的劉邦真是喜出望外。就在龍且的主力楚軍與黥布大戰的時候，劉邦乘著楚軍不能分兵的空擋，趕緊兵出雍地，進襲廢丘——章邯的老巢。
廢丘的水仗
先前平定三秦時，章邯逃回了都城。在雎水戰役時，這個前秦的老將是一箭未發就投降了項羽。他投降就算了吧，還帶著他的人反戈衝亂了整個漢軍聯軍的陣線。使得六十萬大軍瞬間崩潰的最大的罪人就是這個章邯。現在劉邦出來了，他要第一個廢掉這個背信棄義的章邯。大軍二十萬，在大將酈商的率領下，向廢丘出擊。
這個時節正是盛夏，天氣異常悶熱。廢丘地區又已經連續三十天沒有下過雨了。環繞廢丘的狼寧河都已經乾涸地見底了。廢丘的軍民現在是吃水也感到很困難。劉邦的大軍，在張良的參謀下，在酈商的率領和劉邦本人的親自督導下，用強行軍的速度向廢丘進發。
而在大隊來到廢丘之前，酈商已經派遣了一千輕騎，攜帶大量的麻布口袋和鐵鏟等物在狼寧河上游準備攔截河水。
廢丘的守衛士兵其實是看見他們的動向，也明白他們想幹什麼的。但是，他們想，我們現在就是河水也沒有。河床都是乾涸的。你的麻袋拿去可以幹什麼啊？攔空氣啊！他們也就懶得報告將軍。
將軍都不知道，雍王章邯也就更加無從知道了。用了一個整整一個晚上的時間，那一千輕騎把一條狼寧河給堵塞得水瀉不通。
劉邦的後續部隊沒有經過廢丘的外圍，而是繞道直接去了廢丘附近，狼寧河旁邊的一座小山丘。這山丘上也有雍王的小股了望部隊，他們是負責只要發現敵情就立刻用烽火報警的人馬。當然，也就沒有派多少人了。大約也就是相當於現在一個排的兵力。
酈商在探馬探知了這股敵人的存在後沒有再讓部隊繼續前進了。而是派出一百精壯的士兵，挑著好水、好酒和菜蔬，裝扮成販子，唱著秦腔就去了那小山丘。那些負責瞭望的官兵看見了酒水菜蔬，一個個簡直是喉嚨裡也要伸出爪子來了。他們紛紛湊份子，買了一桶酒，要了一桶水，還買了寫下酒菜，慢慢地品酌起來。而那些販子依舊唱著秦腔，慢悠悠從山秋那邊下去了。
在半個時辰後，那些守衛的士兵就不會再動彈了。他們被藥麻翻了。在他們清醒過來前，嘴巴就被堵了個嚴實，手腳也被捆綁起來。劉邦的大軍立即把個山丘駐紮得滿滿噹噹的，連個插針的地界也沒有了。
就在劉邦大軍秘密抵達廢丘的當天晚黑，狼寧河的上游是陰雲密佈，轉眼間便是雷霆萬鈞，再接著就雨箭亂射。狼寧河的河水頓時暴漲起來。而這次下雨在廢丘卻沒有絲毫雨意，那裡的天氣還是那樣悶熱。那些熟睡的雍王士兵根本不知道他們已經在面臨一場大難了。
就在這些士兵熟睡的時候，負責看護上游獨水的人馬接到抽開麻袋的指令。大水，已經憋壞了的大水向億萬頭的野狼，發瘋似地向廢丘衝去。也就在河水即將抵達廢丘的瞬間。在山丘上的士兵，迅速地把他們手裡的麻袋堵住了狼寧河的下游。在河水瘋狂地衝到下游的時候，它們發現河道已經沒有了。本來已經發怒的河水是更加地暴怒起來。他們在發怒的間隙，猛可間發現旁邊還有一條捷徑。喜滋滋的大水頓時往廢丘城衝去。廢丘，在就是片刻間成為一片汪洋……
廢丘城頭升起一片白色降幡。這水本來就是陣雨的結果，是來得快，去得也快。大水很快退去。劉邦現在又一次面對再次要投降的章邯。而章邯雖然下令部隊投降了，他自己卻是依然筆立著，沒有絲毫要過來見劉邦的意思。只見章邯，全身上下白盔白甲、一襲雪白的戰裙，加上花白的鬍鬚。他一手持長槍、一手橫握寶劍，只見他對天大笑幾聲：「先帝啊，微臣追隨你來了。」就看見章邯斗大的人頭骨碌碌地向前滾動了十多步，而章邯的身軀在夏天炎熱的夜空下卻堅持沒有倒下。他的手扶著長槍，一個無頭將軍，像鐵鑄的象，雖然是有點歪斜，卻還是屹立著、屹立著……
劉邦終於明白了這個三番五次投降的秦將的心意了，他是想利用諸侯的仇隙來達到他重建大秦王朝的目的。這真是一個堅韌、忠勇的將軍啊！劉邦對著章邯的屍體連續地鞠了九次躬，又說將來建立漢朝後一定要讓秦地繁榮，不讓血液繼續因為戰爭為白流。然後，在劉邦的號令下，漢均二十萬集體向章邯的屍身鞠躬。在過了又是半個時辰後，那鐵鑄的無頭將軍才轟然地倒地了。堅實的城牆上也給砸出一個深深的坑凼。
廢丘被攻下了，劉邦把這個地方更名為槐裡。然後命令在這裡設置官府和留置官員。以便在四時可以祭祀蒼天、河川和死難的英靈。在辦完這一切後，劉邦的大軍又向前開拔而去。
黥布這邊跟龍且的大部隊僵持了幾個月，拖住楚軍主力部隊的任務也算完成了，於是就想帶兵撤退到漢國。可又怕楚國的軍隊攔截殺掉他，所以，就和隨何從隱蔽的小道逃歸漢國。
黥布到時，劉邦正坐在床上洗腳，就叫黥布去見他。黥布見狀，怒火燃胸，後悔前來，想要自殺。當他退出來，來到為他準備的賓館，見到帳幔、用器、飲食、侍從官員一如劉邦那麼豪華，黥布又喜出望外。於是就派人進入九江。
這時楚王已經派項伯收編了九江的部隊，殺盡了黥布的妻子兒女。黥布派去的人找到當時的寵臣故友，帶著幾千人馬回到漢國。劉邦又給黥布增加了兵力一道北上，到成皋招兵買馬。漢四年七月，劉邦封黥布為淮南王，共同攻打項羽。
雖然被項羽追得滿世界跑，可劉邦還是抽出時間來搞宣傳。「關中王」的名號已經叫了很久，自己還沒立王儲呢！於是在這一年的六月立孝惠為太子，大赦罪犯。讓太子守衛櫟陽，把在吳中的各諸侯的兒子也都集中到櫟陽來守衛。