項梁聽說東陽縣的陳嬰已經取得了縣城，便派使臣去聯絡他，想與他聯兵一同西進。陳嬰原本是東陽令史，居住在縣城裡，平日裡誠信嚴謹，被尊為長者。陳勝起義以後，東陽縣的年輕人殺死了該縣的縣令，聚集了數千人。大家想要推舉一位首領，但是沒有合適的人選，於是便讓陳嬰擔任他們的首領。陳嬰極力推托，認為自己沒有這個能力，最終還是被眾人強行擁立為首領。縣內隨從起義的人很快達到了兩萬人，大家又準備擁立陳嬰為王。陳嬰心裡害怕，拿不定主意，這時他的母親又對他說：「自從我成為你們陳家的媳婦，就沒有聽說過你的先人裡出過貴人，如今你突然得到如此大的名分，這是不吉祥的徵兆啊。你不如及早歸降於別人，這樣的話，大業成功，你依然能夠封侯顯貴，而一旦大業失敗，你也易於逃亡，因為自己不是被世人注意的人。」聽了母親的話，陳嬰就更加不敢稱王了。他對手下人說：「項氏家族世代擔任將軍，是楚國的名門。如今各位想要創建大業，只有依靠項氏的領導才能夠成功。」眾人聽從了陳嬰的意見，全部歸從了項梁。
項梁渡過淮河以後，英布、蒲將軍也率領著各自的軍隊歸降了。項梁統領的軍隊達到了六七萬人，全駐紮在下邳（今江蘇睢寧縣西北）。後來，項梁又擊敗了擅自擁立為楚王的秦嘉，併合並了他的部隊。同時，項羽率領的另一支部隊也經過激烈的戰鬥攻下了襄城，前來會合。聽說陳王已死，項梁便在薛縣召集各位將領商議大事。此時，沛公也從沛縣起兵反秦，並前來歸降。
范增獻計
居巢人范增，擅長謀劃奇計。當項梁的軍隊駐紮在薛縣的時候，陳勝在與秦軍的作戰中失利。范增便前來勸導他說：「陳勝的失敗是理所當然的事情。以前秦國滅亡了六國，其中，楚國是最沒有罪過而慘遭滅亡的國家。自從楚懷王出使秦國而被扣留，楚國人至今還在同情懷念他。因此，楚南公曾經說：『楚國即使只剩下了三戶人家，那麼滅亡秦國的也一定是楚人。』如今陳勝首先起義，他沒有擁立楚王的後代卻自立為王，他的勢運必定不會長久。將來肯定會慘敗的。現在您在江東起兵後，楚國各地將領蜂擁而至，爭先來歸附您，這是因為你們項氏世代擔任楚國將領，他們相信您能夠擁立楚王的後代。」
項梁覺得范增的話言之有理，認為要想得到楚人支持，必須先擁立楚王的後代。於是他採納了范增的建議，派人到民間去尋找楚懷王的孫子熊心。當時，熊心已經落魄到了為人家牧羊的境地，盡避如此，項梁找到他後還是擁立他為王，仍舊稱他為懷王，以順應楚國民眾的願望。而陳嬰被任命為楚國的上柱國，得到了五個縣的封地，和懷王一同居住在楚國都城於台；項梁則自號為武信君。
驕兵必敗
項梁在薛縣停住了幾個月以後，率領軍隊進攻亢父（在今山東省濟寧市），又和齊國的田榮、司馬龍且率領的軍隊一同援救東阿（在今山東東阿附近），並且在東阿打垮了秦軍。同時，項梁派遣項羽和沛公劉邦率領另一支部隊攻打城陽。奪取城陽以後，這支軍隊繼續向西進攻，在濮陽（在今河南濮陽附近）東部地區再次擊敗了秦軍；後來，項羽等人又在雍丘（今河南杞縣）大破秦軍，斬殺了秦將李由。
此時，項梁從東阿西北起兵，來到定陶（在今山東菏澤境內），再次打敗了秦軍。接連的勝利，使得楚軍更加輕視秦軍，軍隊裡的驕傲情緒很快地滋長，認為現在秦軍已經不堪一擊了。謀士宋義看出來了軍隊裡的驕傲情緒，覺得非常危險，就對項梁勸諫說：「我們軍隊雖然取得了接連的勝利，但也因此使將領們驕傲、士兵們怠惰。如果不加以制止的話，這支軍隊遲早會遭到失敗。如今我軍中出現了這樣的現象，而秦軍則在一天天增強，我替您感到憂慮啊！」項梁則認為宋義的擔心是多餘的，沒有聽從他的勸諫，並且對他感到了厭煩，便派他出使齊國。