很快，沛公劉邦依靠原來的兄弟們幫忙，在沛縣拉起了兩三千人的隊伍。不得不說，劉邦的運氣實在不錯，他的哥們兒不僅組成了一個素質很高的群體，裏麵包括蕭何、曹參、樊噲、婁敬、任敖、周昌、周勃、夏侯嬰等後來漢朝的開國重臣，而且這些人絕大部分對劉邦十分認可。
既然隊伍組建完畢，為圖個彩頭，按慣例，劉邦自然也要自我標榜一番。於是劉邦就成了赤帝的兒子(讓劉大爺情何以堪？)，並且宣稱自己曾經斬殺過化作大白蛇的白帝的兒子；又說當年秦始皇也常認為東南方也就是劉邦所在的楚地有天子氣，所以嬴政才到南方巡遊，目的是壓製這股氣息，這樣劉邦在芒碭山裏鑽山溝的原因也就由躲避朝廷的逮捕變成了躲避嬴政在氣息上的迫害。這樣一來，劉邦以往那些所作所為的性質就完全不同了。雖然劉邦還是那個人，做的事也還是那些事，但格調高了很多。
一通動作下來，劉邦順利地拔高了自己的聲望，把自己的造反之舉說成上天注定的事情。最後，赤帝的兒子、渾身上下散發著五彩雲氣的真命天子劉邦在沛縣帶頭祭祀黃帝和戰神蚩尤，宣布早已注定的戰爭的到來。
一切準備就緒，秦二世二年(公元前208年)十月，劉邦的隊伍整裝開拔。話可以說得天花亂墜，但打仗還是得靠劉邦自己。即便劉邦成了赤帝的兒子，有神仙在後麵撐腰，也不代表他一定會順利。毫無指揮和作戰經驗的劉邦一開始連續在胡陵和方與兩個地方碰壁吃癟。他帶著隊伍浪費了不少時日，轉悠了一圈毫無收獲，隻好回到豐邑繼續招兵買馬。雖然接連出擊失敗，但劉邦的公開造反行為還是刺激了朝廷。很快，泗水郡郡監 (官職)某平(史失其姓)便帶領軍隊包圍了豐邑。
沛縣隻是一個小縣，下轄的豐邑更非一座堅城，劉邦手下這兩三千人不可謂多，城外黑壓壓一片的秦軍又不可謂少，而且這是劉邦第一次被敵人包圍(以後他還要多次麵臨這種情況)——這一切都預示著劉邦軍事生涯麵臨的第一次考驗異乎尋常地難。如果換作一個普通的義軍將領，接下來的事情十有八九就是要出城投降了。但劉邦就是這麽不尋常。