渡過長江之後，項梁和他所率領的大軍開始向北前進。一路上不斷地吸收大小流民群體，隊伍不斷壯大。
「項梁將軍可是位了不起的人物。」
這一評價飛快地傳向四面八方。也許跟項梁本是亡楚項燕將軍的遺孤多少有些關係，但更重要的還是其為人方面具有獨特的品格，而且好像總有點神秘莫測。
可惜的是，項梁並沒有威武雄壯的身軀。在當時，身為將軍的人要麼是身材高大、生性強悍，要麼是長著一副怪相，讓人覺得像個仙人，項梁要是能有其中的一條就很理想了。一眼看去只像個老書生的項梁，在這點上就缺乏令百萬之眾景仰的條件，然而只要稍加留意，就可彌補此項不足。那就是盡量避免將本來面目暴露於眾目睽睽之下。
「怎麼，那就是項梁啊？」
只要人們內心產生一點點失望的情緒，有時就會使一支幾萬人的隊伍的豪情壯志霎時間一落千丈。
這一點項梁早已心中有數。所以行軍過程中，項梁總是坐在類似先前始皇帝曾坐過的那種輥瓊車裡。他坐在車上制定作戰計畫，向各路將領發布命令，在上面吃飯，有時中午還要睡上一覺。
「我的身體也開始遲鈍啦！」
偶爾，項梁也不得不在內心裡發出這樣的感慨。年輕時曾練過劍術的身體，經過長期的流浪生活，也變得不敏捷了，很可能還和年齡有關。整天搖搖晃晃地坐在車裡，累得好像腰都要斷了。太累是會積勞成疾的。人一疲勞就會萎靡不振，即使還能堅持，也不免會有心灰意冷的時候。
「恐怕再也不會有什麼作為了吧？」
他時常陷入這種茫然的思緒之中，退意萌生。縱使不能將秦徹底推翻，只要把楚重新振興起來，也總算有了交待，僅此足矣！這種很難向他人傾訴的想法一直縈繞在他的心頭。
每當大軍因進展緩慢而長期在某處安營紮寨時，他就會經常不見蹤影。
找的借口則是「不出外走走反而會更加疲勞」，不過這好像更符合他性格上那根深蒂固的怪癖，倘若不偶爾獨處一段時間，心情就會抑鬱得近乎發狂。
日落前後，他換上普通農民的裝束，趁著黃昏鑽進入士兵堆里，或者借著落日餘暉在山野間快步走上一段，這時就會體驗到一種全新的感覺，彷彿像一條可愛的魚兒又重新回到江河之中，搖頭擺尾地暢遊了一番。
就是這位項梁，當大軍渡過淮水向北推進之時，望著北岸遠處一片綠油油的景象，不禁渾身充滿了豪情壯志。
只要渡過淮水，腳下就不再是人文粗放的南方蠻荒之地。可稱為漢民族文明中心的中原地區已近在咫尺。遙遠的北方有滔滔黃河滋潤的遼闊大地。淮河即位於其南部，黃河與淮河之間的廣大平原地帶，自古以來就由這片大地上的原住民長期耕耘，可以說乃是一個群雄爭霸的文明的大舞台。總之，淮河是中國的南北分界線。
「南部的長江太大。真正造福於人的河流還是這條淮河。」項梁在想。黃河自西向東流去，淮河也流向東方。而在黃河與淮河之間有無數密如蛛網的河流，有的向北流去，有的往南流淌，每一條河的兩岸都有許許多多發達的大小城鎮。項梁及其所率大軍就正要踏人這片地帶。渡過淮河之後，項梁沒過多久便聽到了一個人的名字，他叫「黥布」。所謂黥，就是塗抹上黑墨水的意思。只有居住在江南的非漢民族，例如越人，才會將黑墨汁塗到臉上或身上，再潛人水裡去捕撈魚類貝類等水中生物。然而漢民族卻沒有這種所謂的蠻風蠻俗，一說施黥之人則必定是個囚犯。黥布是六（安徽省境內）那個地方的人，本來姓英，名字布本是貨幣的一種，所以很好記，在六是位頗有名氣的人物。
英布雙肩像兩座小山似的高高聳起，力大無比，生性粗野，發起脾氣來暴躁得像只老虎。從小時候起，他給人的感覺就不像是一個可以安安生生一輩子的人。對他那副長相，也曾有人作過預言：這孩子長大以後可能成為黥首之人。然後又補充了一句：「受刑之後，當可為王。」
英布特別喜歡帶領一幫流氓夥伴橫行霸道，終於被秦官吏抓捕施以黥刑，又與其他囚犯一起，被繩捆索綁驅趕到始皇帝驪山陵墓的施工現場。很快，他就在囚犯同夥中間成了一個頭領，沒過多久，「黥之布」在釃山工棚里就已經大名鼎鼎了。
「黥布」這一稱呼，就是在工地上產生的。大約在陳勝起義前後，黥布逃離了工棚，率領追隨他的囚犯們輾轉各地，干一些盜賊的勾當，又企圖在更大範圍內收攏流寇。為此他想到必須抬出一位有聲望的人。鄱陽縣有一位叫吳芮的縣令，被人們尊稱為「鄱君」。黥布便去拜見這位人物，扛著這個人的旗號去進一步擴展自己的勢力。在此期間，他知道了亡楚遺臣項梁的名字，又了解到項梁正率領江南健兒北上，其聲勢與日俱增，遂派出使者去毛遂自薦。
「黥布啊？」
項梁從這個有點嚇人的名字里對其人有了初步印象，接著又從使者那裡聽到這個人的本事和品行，便愈發充滿了期待。在當時，軍隊裡面很需要猛獸般的沙場戰將，他們都能衝鋒陷陣，面對敵軍的營壘，能無堅不摧、無攻不克。說到項梁這支大軍，幸好有他的侄子項羽。然而當進行幾個方面的作戰時，僅有項羽一人是不夠的，還會造成更為嚴重的不利局面：因為只有項羽一支軍隊勇往直前，其他部隊就會被甩在後面，這樣反而會給作戰帶來麻煩。同時有幾員猛將才是最理想的。
不久黥布就來了。第一眼看到他時，項梁就被深深打動了，心裡嘟嚷了一句：「這簡直是人間的一大怪物。」
項梁備上酒肴，與黥布共度了一個晚上。黥布話語不多，只是一個勁兒吃東西、喝酒，對酒席桌上作陪的諸位將軍的言論也只是綳著臉聽著。
項梁有點擔心起來，這傢伙該不會是個傻瓜蛋吧？然而講到關鍵處時，黥也會露出極為開心的笑容。
「不是傻瓜蛋。」
項梁放心了。別人講到什麼地方時才會感到好笑，憑這一點就能看出一個人的格調，這是項梁觀察人的一個方法。
項梁對黥布給予了極高的待遇，把他跟項羽一起任命為先鋒大將軍。
項梁軍規模愈來愈大，其勢頭有增無減，只好暫先選定下邳（江蘇省境內）為根據地。
下邳正面對泗水，直到今天，仍然叫做邳縣。早在春秋戰國時，下邳就已十分繁華，最能顯示其繁華程度的是它做過邳國的國都，到秦朝才變成了縣城。在歷史上，這可是一座名城。
在此期間，有一位歸屬劉邦，日後又成為其謀臣的軍事家張良（字子房），就曾與這座小城有過一段因緣。曾為韓貴族的張良早前欲剌殺秦的始皇帝，遂雇一力士，企圖以一百二十斤重的鐵鎚偷襲始皇帝的座車，在博浪沙襲擊了一次，但沒有成功。張良連忙逃跑躲藏起來，後來又更名改姓藏匿到這座下邳城，整天與城裡的地痞無賴廝混在一起，其間曾見到過一位年事已高的隱士黃石公，並得到了一本兵書。
不用說，項梁在此期間既不知道張良這位令人畏懼的軍事家的名字，也不知道其人的存在，對他後來在劉邦手下令項羽大為頭疼的種種事實，更無從得知了。
當項梁還以下邳為大本營時，突然得到了一份令人吃驚的情報。
「陳勝大敗，去向不明。」
報告者又說：「擊潰陳王軍的，乃是秦的章邯將軍。」
不過，對項梁來說，章邯的名字倒不必介意。他最關心的是陳勝，因為陳勝是亡楚的代表，立國號為「張楚」，任命項梁為上柱國，僅憑這兩件事，項梁就該稱其為主公，儘管他還從未拜謁過這位主公。當然，這項上柱國的任命也只不過是浪蕩於世間的召平的一個騙術，作為當事者的陳王並不知情，這對項梁來說並不重要，重要的是，本來不久就要與其會師的陳王及其勢力竟被消滅了，這才是當前最大的現實。
「該如何是好呢？」
項梁在原縣令居住的深宅大院里獨自思索著，卻沒有結論。項梁本是一個深謀遠慮的人，不過並不能在瞬間憑感覺機敏地作出結論，遇事總是要經過長時間的思考，有時則需絞盡腦汁冥思苦想。這種時候，他看上去完全像一個懶漢，直到日出三竿還在睡懶覺，整天像根細木棍似的躺在床上，有時猛抓住睾丸用力拉扯，有時還會獨自一人放聲大笑，那形象簡直就像個痴漢。
就這樣，日子飛快地過去。陳王的生死仍舊不明。不久又得到情報，說陳王原屬下一個叫秦嘉的人，將一位名叫景駒的人物立為楚王了。
「陳勝原來是被這幫傢伙給殺死啦！」
直到這時，項梁腦海里才莫名地冒出了這個想法。
「假定陳勝已經死掉，我就該是亡楚的代表了吧？」
項梁在考慮這個問題。儘管必須歷經百戰方能讓世間承認這一事實，但項梁就是抱住這個念頭不放。令世間承認自己的途徑只有一個，那就是跟秦的官軍決戰，將其擊垮。