計劃去投奔魏公子信陵君。他早就聽說很多人跟著信陵君，不愁吃穿。
魏國的公子信陵君魏無忌竊符救趙，這樣的英雄故事很快傳遍天下，成為大家的偶像。
信陵君魏無忌最大的特點是禮賢下士，不管你出身如何，隻要有本事，都能得到他的禮遇和重視，比如侯嬴和朱亥，一個是看門人，一個是屠夫，可是信陵君把他們待為上賓，結果他們在信陵君竊符救趙時發揮了重要作用。
也就是說，信陵君是劉邦最崇拜的人，他想去投靠。想當信陵君的幕僚，混口飯吃。可惜劉邦風塵仆仆的趕到大梁時，才知道信陵君早就死了。不過沒有關係，信陵君的徒弟張耳好像混得不錯，去投靠也好。
不過張耳在外黃，也就是現在的河南省商丘市民權縣的地方，距離大梁有一兩百裏地。
劉邦一路乞討著去了，風餐露宿的，饑一頓飽一頓，磨練了他的意誌。
到了大黃見著張耳，跟著張耳混了幾個月，長了不少見識。《史記·張耳陳餘列傳》中記載“高祖為布衣時，嚐數從張耳遊，客數月。”
這種好日子沒過多久，魏國就被秦國被滅了，張耳成了秦國的通緝犯，門客都溜了。劉邦也灰溜溜的回到了豐縣。
他爹劉煓已經娶了小老婆，生了他同父異母的弟弟劉交，正在樂嗬嗬地享受第二春呢，壓根就顧不上他。
再說，他也沒臉回去。在道上混的人，都注重自己的臉麵，他還沒混出個人樣，怎麼好意思回去呢？
可是肚子咕嚕嚕的叫著，思前想後：我大哥平日待我不錯，去他那裏找吃的。
好在他大哥劉伯憨厚，不顧妻子的反對，收留了他。劉邦在大哥家蹭吃蹭喝，沒少遭大嫂的白眼，不過他臉皮厚，不在乎。可惜這種好日子也沒過多久，他哥劉伯很快就生病死了嫂子怪他是喪門星，把他趕了出去。
劉邦念著大哥這點好處，在當了皇帝之後，追封劉伯為武哀王，長嫂封為陰安侯，侄子劉信為羹頡侯。
從大哥家出來後，劉邦沒有去二哥家，也沒有回去找他爹，而是一頭紮進了一家酒館，想讓自己先醉一次。
那家酒館是一個叫武負的寡婦開的，那年代能夠開酒館的，都不是什麼善良之輩，因為不但經常有人喝酒鬧事，還有人會喝霸王酒，喝酒不給錢，欠到猴年馬月都不還。
都說寡婦門前是非多，武負這個長得有幾分姿色的寡婦，平時就和一些男人不清不楚。劉邦原來當流氓頭的時候，武寡婦多次勾引他，都沒有勾引上手，倒是被他欠下了不少酒錢這就是史記中“武負貰酒”的來曆。
劉邦原先在酒館中喝酒，除了和武負打情罵俏之外，還與一個叫王媼的女人不清不楚。
但那都是過去的事情了，誰年輕的時候沒有瘋狂過呢？
他現在是遊曆後歸鄉的遊子，類似於現在海歸，自我感覺多少是有些身份的人。
於是奇妙的情景出現了：武負靠在門邊，雙目直勾勾的望著劉邦，口中道：“回來了？”
劉邦點頭：“回來了”武負說：“進來喝幾盅？”劉邦坦然走了進去。幾盅酒下肚之後，劉邦借著酒勁對直勾勾望著他的武負說：“我想在你這裏住一段時間！”
那一刻，武負的臉上樂開了花，她苦苦期盼的奇跡終於出現了。（欲知劉邦怎麼和一個寡婦糾纏，請看下一節）