与韩信北伐魏、赵同时，刘邦根据张良的建议，立即派人南下游说英布，以便进一步孤立项羽。然而，刘邦派往九江的使臣，却在六县（今安徽六安）被供养起来，一连三天，英布都不肯见他们。这位使臣就是刘邦的谒者随何。

刘邦在彭城大败之后，从下邑（今河南砀山）移军砀县，不久又退到虞县（今河南虞城北）。于是，刘邦对着部属说道：“谁能为我出使淮南，让英布发兵攻打楚军？”又说：只要他在齐国再拖住项羽几个月，我夺取天下就没有问题了。

刘邦如此重视英布，事情并非偶然。原来，英布自从投奔项梁之后，一直是楚军一位猛将。项梁死后，他成了项羽手下的一名将领，常常跟随项羽冲锋陷阵，出生入死。项羽率军北上救赵，英布被任命为将军。他几次击败秦军，是巨鹿之战的有功之臣。英布骁勇善战，常常以少胜多，为楚军争得了声誉。项羽在新安坑杀20万秦军的降卒，英布就是具体执行者之一。秦王朝灭亡后，项羽率军西进关中，刘邦派兵扼守函谷关，企图拒项羽军于关外，还是英布率先从小道破关而入。所以，项羽分封诸侯，英布战功赫赫，被封为九江王。直到公元前206年八月，英布还根据项羽的密令，派人击杀楚怀王于郴县。英布对于项羽，可谓言听计从，也确实立了不少战功。但是，到了田荣起兵，项羽北上攻齐，命令英布派兵支援，英布却托病未行，最后只派4000人去应付。刘邦攻占彭城，项羽急如星火，英布又借故有病，不肯出兵帮助。从此项羽恨之，几次派人责备英布，还让英布去见他。英布深惧项羽，不敢前往。因为当时诸侯纷纷起兵，项羽忙于对付，想利用英布的力量，才没有进行军事报复。刘邦想利用英布与项羽的矛盾，因此在彭城战败之后，决定联合英布，共同对付项羽。

随何知道刘邦的意图，便自告奋勇，表示愿意出使淮南。公元前205年四月，刘邦派了20个人，跟随何一起南下。

随何到了六县，英布让主管膳食的太宰招待他们，却不肯跟随何见面。三天过去了，随何无可奈何，只好先说服太宰，请他帮忙求见英布。

英布果然被说动了。见面时，随何开门见山，劈头就提出他与项羽的关系。英布毫不犹豫，宣称自己是楚王的臣子。英布言不由衷，随何心中有数。他说：“大王与楚王同是诸侯，却自称是楚王的臣下，无疑认定楚国强大可以‘托国’。”接着，随何列举他们之间的矛盾，指出项羽北上攻齐，英布只派4000人支援，这哪像为人臣子。刘邦攻取彭城，项羽还在齐地，英布本应出兵与项羽会战彭城，但是英布坐山观虎斗，竟不动一兵一卒，也不像为人臣子的样子呀！最后随何一语道破：英布不过名誉上向楚称臣，实际上想发展自己的势力，他现在不背楚是因为汉弱的缘故。

为了劝说英布归附刘邦，随何分析了楚汉战争的形势。他认为项羽背盟约，杀义帝，负有不义之名。且楚军深入敌国八九百里，战线很长，以致老弱转输粮草于千里之外，士兵疲于奔命。汉王守成皋、荥阳一带，取用蜀、汉之粟，深沟壁垒，分兵防守边塞。所以，只要汉军坚守不动，楚军进退两难，形势对汉军有利。随何又故作姿态，对英布心甘情愿托身于危亡的西楚表示大惑不解。又说：“只要大王发兵背楚，将楚王再拖住几个月，汉军就可以夺取天下了。大王归附了汉王，一定会得到裂地封王，九江还是属于大王所有。”经过随何的劝说，英布私下答应背楚归汉。

当时，项羽的使臣也在九江，住在客舍里，正催着英布发兵助楚。随何见此情景，便直闯客舍，责问项羽的使臣说：“九江王已经归附汉王，你们凭什么让他发兵？”随何见机行事，搞得英布骑虎难下，目瞪口呆。项羽的使臣正要起身，随何顺水推舟，对英布说：“背楚的事既然已经决定，可以将项羽使者杀了，不能让他跑回去，并赶快跟汉军会合。”英布不再犹豫了，他杀了项羽的使者，并起兵攻楚。

项羽得知英布叛楚，立即命令项声、龙且发兵攻九江。几个月之后，龙且破英布军，英布担心遭到不测，便与随何一起从小道跑回荥阳。

公元前204年十二月，英布回到荥阳，刘邦立即召见。当时，刘邦正靠在床上洗脚，表现得十分傲慢，使英布怒不可遏，以致想拔剑自杀。等到英布去住宿地，又别是一番景象，一切帐御、饮食、从官的安排，规格竟与汉王差不多，不禁使英布大喜过望。刘邦使用的这套权术，终于使英布折服了。于是英布派人回九江，率领数千人归汉。

刘邦采用分化瓦解的手段，便英布脱离了项羽。英布背楚归汉，壮大了反楚的力量，削弱了楚军的力量，不但使项羽愈加孤立，而且也解除了刘邦在南翼的后顾之忧。刘邦成功地联合反楚的力量，这是汉军在军事上由被动转为主动的重要原因之一。