黥布原是项王部下勇冠全军的一员猛将，在反秦斗争中曾为项王屡建战功，受封为九江王。汉王二年，齐王田荣叛楚，项王率兵北击齐国，向九江王黥布征调军队，黥布借口有病不肯出征，只是派将领率几千人前往。汉军在彭城打败楚军，黥布又借口有病不去帮助楚国，项王因此而怨恨黥布，多次派使者责备他，并征召黥布。黥布愈发恐惧，不敢前往。当时，项王北方忧虑齐、赵两国，西方担心汉国，亲附项王的只有九江王黥布一人。项羽看重黥布的才能，想要亲近并任用他，所以没有攻击黥布。

汉王于彭城惨败后，于下邑曾向张良问道：“我愿舍弃函谷关以东的土地作为封赏，谁可以与我共同建功立业？”

“九江王黥布，是楚国的一员猛将，与项王有矛盾；彭越与齐王田荣共同于魏地反楚，这二人可以立即使用。而汉王部下的众将领，唯独韩信可以嘱托大事，独当一面。”张良回答说。

汉王从下邑经魏地来到虞（今河南虞城县），对左右的人说：“像你们这班人，不足以与我一道商议天下大事。”汉王手下掌管传达的谒者随何进前说道：“不明白大王所说的是什么意思。”汉王说：“谁能为我出使九江，使令九江王发兵叛楚，把项王拖在齐地几个月，我夺取天下的事就可以周全了。”随何说：“我请求出使九江。”

汉王三年十一月，随何一行二十人来到九江王的都城六，通过九江王的太宰（掌管国王膳食）的介绍，但是过了三天还没有见到九江王，便对太宰说：“大王不接见我随何，必定是以为楚国强大，汉国弱小，这正是我所以出使的原因。假使我能见到大王，说得对，那是大王所要闻知的；说得不对，可以在广场上将我们二十人斩首，用来表明大王背汉而与楚国友好。”

太宰把随何的这段话向黥布汇报，黥布接见随何。随何向黥布说：“汉王派我恭敬地上书大王的驾车人，我私下感到奇怪的是，大王与楚王为什么这样亲近？”

“我是以臣的身份服事他。”黥布回答说。

“大王与项王一同被列为诸侯，却北面向他称臣，必定是以为楚国强大，可以把国家托付给他。项王攻伐齐国，亲自扛着筑墙的器具，身先士卒，大王理应率领九江的全部军队亲自率部下前往，充任楚军的先锋。可是您却只是派四千人去援助楚国。作为北面服事人家的臣子，本来应当这样的吗？汉王攻占彭城的时候，项王还正在齐国作战，大王理应率全部兵力渡过淮河，到彭城下与汉军作战。大王率领万人以上的人马，却无有一人渡过淮河去参加会战，而是袖手观望两家的谁胜谁败。把国家托付给人家的人，应当是这样的吗？大王用空名来依靠楚国，却又想完全依赖自己，我私下认为大王这样做是不可取的。

大王所以不背叛楚国，是以为汉国弱小。实际上，楚兵虽强，在天下人面前却背负着不义的名声，因为他违背盟约又杀害了义帝。然而，项王依仗着作战获胜，自以为强大。可是汉王联合诸侯，回军驻守于成皋（又称虎牢，在今河南荥阳县西汜水镇）、荥阳，运来了蜀郡、汉中郡的粮食，深挖战壕，修筑壁垒，派士卒分守要塞。楚国调回部队后，中间隔着魏国，深入敌国有八九百里。楚军想要攻战而不能得胜，想要攻城又不能得手，不得不用老弱残兵从千里以外运送军粮。楚军到达荥阳、成皋后，汉军坚守而不出战，楚军前进不能攻取，后退又不能脱身，所以说楚军是不足以依靠的。如果楚军战胜汉军，各国诸侯会各自感到危惧而相互救助。可见，楚国的强大，正是招来了天下的兵力同他相对抗。所以说，楚国的形势不如汉国，这是显而易见的。

如今大王不同万无一失的汉国结交友好，却托身于行将灭亡的楚国，我私下对大王感到迷惑不解。我不是认为大王的兵力足以灭亡楚国，我是说大王如果发兵叛楚，项王必定会停留在原地作战。如果项王在原地停留几个月，汉王夺取天下就会是万无一失了。到那个时候，我与大王提着宝剑归属汉王，汉王必定会割地封赐大王。至于原有的九江国，也当然还是归大王所有。所以汉王特派我向大王献上这条计策，希望大王能有所考虑。”

随何的这通长篇大论，说服了九江王黥布。黥布向随何说：“遵命。”暗中答应叛楚归汉，但未敢向外泄露。

当时，楚国的使者正住在九江王都城的客馆里，急着要求黥布发兵。随何为促成黥布立即宣布叛楚，便直接闯入王府，楚使当时正在同黥布谈发兵的事。随何进入后，坐在楚使的上位，说道：“九江王已经归属汉王，楚国凭什么让九江王发兵救楚？”黥布被随何的这一举动弄得大吃一惊，楚使闻言后起身走出。随何趁机向黥布说：“事情既然已经决定下来，可以立即杀掉楚国使者，不能让他回去。我们急速归向汉国，合力与楚军作战。”黥布对随何说：“那我按照你所指教的，起兵击楚就是了。”于是，黥布杀死楚国使者，起兵攻楚。楚国派项声、龙且率兵攻击九江王，项王则留在原地进攻下邑。数月后，龙且击败黥布的军队。黥布想要率领部队逃往汉国，又恐怕项王截杀他，便抄小路与随何一同逃归汉国。

同年十二月，随何与黥布经历千难万险，一同来到汉王军营。当时，汉王正叉着腿坐在床上洗脚，随即召黥布入见。黥布见汉王接见自己时如此傲慢无礼，十分愤怒，后悔自己不该前来归汉。然而既已叛楚，退却无路，想要自杀而死。待黥布走出汉王大帐，来到为自己准备的馆舍，舍内的帷帐以及所用物品、饮食和随从官员的标准同汉王一样，黥布“又大喜过望”。汉王有意这样做，是因为黥布久已为王，恐其日后自尊自大，便对他慢待无礼，折服他的傲气；又以优厚的物质待遇取悦黥布之心，使令他日后忠心为汉国效力。于是，黥布派人去九江，这时项王已派项伯收编了黥布的部队，杀死黥布的妻子儿女。黥布的使者找到黥布的一些老朋友和亲属，率领数千人归属汉王，汉王增拨给黥布一些士兵，同他一道北上，一路上征兵到达成皋。从此黥布便逐渐成为汉王属下反楚大军中一支重要的主力部队。