刘邦在成皋养好了箭伤，回到关中栎阳安抚百姓，四日后返回广武军中。刘邦到栎阳的目的显然不只是安抚百姓，而是通过这个行为给自己做征兵广告，汉军兵源再次得以补充。
龙且被杀、田广被俘，韩信破齐对项羽的打击非常大，这意味着他的大后方出现了问题。同时，彭越又在梁地经常截断楚军粮道，导致楚军虽在广武围困汉军，但后方失守、粮道不稳，并非长久之计。而刘邦虽然被围，但得益于萧何在巴蜀的苦心经营，兵源和粮饷得以不断补充，战略上实则并不处于劣势。此时刘邦心里还有一份牵挂，就是被项羽掳走作为人质的刘太公和吕雉。
项羽损将断粮，又被韩信大兵压境，在这样的局势下，刘邦看到了机会。于是派陆贾前去说服项羽，希望能迎回家人，但未能成功。随后又令侯公，也就是姓侯的一位辩士，再次前往楚军游说项羽，这次不但成功使吕公、吕雉被释放，还与项羽达成协议，以鸿沟为界中分天下，鸿沟以西为汉，鸿沟以东归楚。
项羽以刘邦家人为人质，是极大的政治资本，绝不可能轻易归还，甚至连名士陆贾都无法说服项羽。就是这么一件难于登天的事儿，却被名不见经传的侯公办成了，可想而知，这是一番多么精彩的辩词。但遗憾的是，《汉书》《史记》都没记录候公到底说了什么，给后人留下了很大的想象空间。
一千年后，北宋著名词人苏轼写了一篇《代侯公说项羽辞》，描述了侯公说服项羽的经过。
大概意思就是刘邦志在天下，不会因亲人死活而改变，项羽虽然首先举起反秦大旗，但数年征战下来犯了不少错误，导致如今楚的优势丧失殆尽，如果还不肯归还吕公、吕雉，则会加重汉军的仇恨，为刘邦再增加一条灭楚的理由，不如就此罢兵，共分天下。当朝史官都未记载的细节，被苏轼在一千年后描绘的有声有色，可信度应该不高，权当做后人的一种猜想吧。
苏轼对细节的描写可能只是一种合理的猜测，但对大局势的分析是很值得参考的。巨鹿之战使项羽的名望和实力都到达了顶峰，诸侯无不臣服。可是他目光短浅、用人失当，楚汉实力对比在短短几年内发生了反转。
虽然现在两军在广武都是人困马乏，无力再战，但刘邦手握巴蜀、关中大后方，占据敖仓，韩信一路平定了代、赵、燕、齐，彭越不断的骚扰楚军补给线。如果继续相持下去，汉军的优势会越来越明显。此时是通过和平手段接回吕公、吕雉的最佳时机，如果项羽还是不肯，等刘邦实力恢复起来，必然会遭到更激烈的报复。以刘邦之坚决果敢和心狠手辣，是不可能因为两个亲人而放弃天下的。
九月，项羽如约放归了太公和吕雉，汉军将士大呼万岁。侯公因此立下大功，被封为平国君。
鸿沟之约达成后，项羽罢兵东归，刘邦也准备回到关中。这时，张良、陈平劝谏道：“如今汉已拥有天下之大半，诸侯也都依附于我们，而楚军此时人困马乏、缺少粮草，若不趁机消灭他们，就是养虎为患。”刘邦采纳了他们的建议。
这就是所谓兵不厌诈，为了争夺天下，可以撕毁已经达成的约定，尽管这非常不上台面，但终究是帮助刘邦取得了天下。因为谁也不敢说，放项羽东归之后，他又会在哪一天又卷土重来。正如杜牧的诗句，江东子弟多才俊，卷土重来未可知。
汉五年十月，刘邦带兵追击项羽到阳夏南，准备与齐王韩信、魏国国相彭越的军队会师后，共同攻击楚军。但一直走到了固陵，还没遇到这两路大军。楚军趁机大败汉军，刘邦撤退，坚壁不出。
刘邦对此感到很郁闷，就问张良：“这些诸侯都不听话，可咋办呢？”这是刘邦的特点，遇到难题就问手下，这咋办，那咋办。好在刘邦帐下谋士如云，他自己也善于听取建议。
张良说：“我们已经基本击败了楚军，但还未对这些功臣进行分封，所以他们不来也觉得理所应当。如果大王能与功臣们共分天下，他们自然就会听话。立韩信为齐王并非大王本意，韩信他自己也非常清楚；而彭越攻下梁地，因为这里最初封给了魏豹，他只能做个相国，如今魏豹已死，大王却未能尽早封他为王。建议大王最好把睢阳以北至谷城的地盘封给彭越，把陈以东至海边的地盘封给韩信，韩信的家在楚地，也正合他的本意。如此，两人就都为自己而战，击败楚军就很容易了。”刘邦听从了陈平的建议，派使者前往韩信、彭越军中传达封王的命令。得到了刘邦的分封，两人果然都带着兵马前来相助。
十一月，刘邦派堂兄弟刘贾南渡淮水进入楚地，围困寿春。同时，汉军还派人前往楚军，成功的策反了大司马周殷。周殷叛变原因至今未出现在任何史书记载中。陈平曾点名指出项羽的四大“骨鲠之臣”：亚父范增、钟离眛、龙且以及周殷。由此可见，周殷官至楚军大司马，绝不是个小人物，说服周殷反叛肯定不是容易的事。
但周殷的叛变似乎非常干脆，因为他马上就用舒县的兵屠了六县，还率领九江郡的楚兵配合英布屠了城父（fǔ），并随刘贾与刘邦会师。这引起了后世的无限猜想，是不是项羽曾经严重的得罪过周殷，才导致他一有机会就头也不回的叛离了楚。
历史的真相我们已不得而知，但非常清楚的是，周殷的叛变对项羽是致命的。因为楚国的首都彭城北有韩信，西有彭越，两人均接受了刘邦的分封，如今南部地区因周殷叛变也归了汉军，楚军被压缩在很小的一块区域内，形势岌岌可危。
项羽背约被刘邦指责为“项羽十罪“之首，还曾以此号召诸侯共同反楚，而如今自己却故技重施。这背后依然是实力的保障，弱者才用盟约自保，而强者只靠实力说话。
所以，哪有什么绝对意义的正义之师，不过是斗争者彼此的攻讦手段罢了。