楚使者在，方急責英布出兵，舍傳舍。隨何直入，坐楚使者上坐，曰：“九江王已歸漢，楚何故得出兵？”布驚詫。楚使者起。何因說布曰：“事已構，可遂殺楚使者，無使歸，而疾走漢併力。”布曰：“如使者教，因起兵而擊之耳。”於是殺使者，因起兵而攻楚。楚使項聲、龍且攻淮南，項王留而攻陷邑。數月，龍且擊淮南，破布軍。布欲引兵走漢，恐楚王殺之，故間行與何俱歸漢。
遂西，與上兵遇蘄西會甀。布兵精甚，上乃壁庸城，望布軍置陳如項籍軍，上惡之。與布相瞥見，遙謂布曰：“何必而反？”布曰：“欲為帝耳。”上怒罵之，遂大戰。布軍敗走，渡淮，數止戰，倒黴，與百餘人走江南。布故與番君婚，以故長沙哀王令人紿布，偽與亡，誘走越，故信而隨之番陽。番陽人殺布茲鄉民農家，遂滅黥布。
陳勝之起也，布乃見番君，與其眾叛秦，聚兵數千人。番君以其女妻之。章邯之滅陳勝，破呂臣軍，布乃引兵北擊秦擺佈校，破之清波，引兵而東。聞項梁定江東會稽，涉江而西。陳嬰以項氏世為楚將，乃以兵屬項梁，渡淮南，英布、蒲將軍亦以兵屬項梁。
淮南王至，上方踞床洗，召布入見，布大怒，悔來，欲他殺。出就舍，帳禦飲食從官如漢王居，布又大喜過望。於是乃令人入九江。楚已使項伯收九江兵，儘殺布老婆。布使者頗得故交倖臣，將眾數千人歸漢。漢益漫衍兵而與俱北，出兵至成皋。四年七月，立布為淮南王，與擊項籍。
項梁涉淮而西，擊景駒、秦嘉等，布常冠軍。項梁至薛，聞陳王定死，乃立楚懷王。項梁號為武信君，英布為當陽君。項梁敗死定陶，懷王徙都彭城，諸將英布亦皆保聚彭城。當是時，秦急圍趙，趙數令人請救。懷王使宋義為大將，範曾為末將，項籍為次將，英布、蒲將軍皆為將軍，悉屬宋義，北救趙。及項籍殺宋義於河上，懷王因立籍為大將軍，諸將皆屬項籍。項籍使布先渡河擊秦，布數無益，籍乃悉引兵涉河從之，遂破秦軍，降章邯等。楚兵常勝，功冠諸侯。諸侯兵皆以服屬楚者，以布數以少敗眾也。
漢三年，漢王擊楚，大戰彭城，倒黴，出梁地，至虞，謂擺佈曰：“如彼等者，無足與計天下事。”謁者隨何進曰：“不審陛下所謂。”漢王曰：“孰能為我使淮南，令之出兵倍楚，留項王於齊數月，我之取天下能夠百全。”隨何曰：“臣請使之。”乃與二十人俱，使淮南。至，因太宰主之，三日不得見。隨何因說太宰曰：“王之不見何，必以楚為彊，以漢為弱，此臣之所覺得使。使何得見，言之而是邪，是大王所欲聞也；言之而非邪，使多麼二十人伏斧質淮南市，以明王倍漢而與楚也。”太宰乃言之王，王見之。隨何曰：“漢王使臣敬進書大王禦者，竊怪大王與楚何親也。”淮南王曰：“寡人北鄉而臣事之。”隨何曰：“大王與項王俱列為諸侯，北鄉而臣事之，必以楚為彊，能夠讬國也。項王伐齊，身負板築，覺得士卒先，大王宜悉淮南之眾，身自將之，為楚軍前鋒，今乃發四千人以助楚。夫北麵而臣事人者，固如果乎？夫漢王戰於彭城，項王未出齊也，大王宜騷淮南之兵渡淮，日夜會戰彭城下，大王撫萬人之眾，無一人渡淮者，垂拱而觀其孰勝。夫讬國於人者，固如果乎？大王提空名以鄉楚，而欲厚自讬，臣竊為大王不取也。但是大王不背楚者，以漢為弱也。夫楚兵雖彊，天下負之以不義之名，以其背盟約而殺義帝也。但是楚王恃克服自彊，漢王收諸侯，還守成皋、滎陽，下蜀、漢之粟，深溝壁壘，分卒守徼乘塞，楚人還兵，間以梁地，深切敵國囗囗囗百裡，欲戰則不得，攻城則力不能，老弱轉糧千裡以外；楚兵至滎陽、成皋，漢死守而不動，進則不得攻，退則不得解。故曰楚兵不敷恃也。使楚勝漢，則諸侯自危懼而相救。夫楚之彊，適足乃至天下之兵耳。故楚不如漢，其勢易見也。今大王不與萬全之漢而自讬於危亡之楚，臣竊為大王惑之。臣非以淮南之兵足以亡楚也。夫大王出兵而倍楚，項王必留；留數月，漢之取天下能夠萬全。臣請與大王提劍而歸漢，漢王必裂地而封大王，又況淮南，淮南必大王有也。故漢王敬使使臣進愚計，願大王之留意也。”淮南王曰：“請受命。”陰許畔楚與漢，未敢泄也。