刘备入主徐州惹怒了一个人，袁术。
听说刘备取代陶谦当了徐州刺史，并一改与自己结盟的现状转投袁绍，这让袁术无法释怀。袁术一向心高气傲，本来就瞧不起刘备，他曾对人说：“我袁术生平还从来没有听说过天下还有刘备这个人！”
袁术说干就干，率兵挥师北上，直取徐州。刘备不敢怠慢，赶紧整顿人马南下迎击，双方在徐州刺史部南部的下邳国、广陵郡一带交战，这里就是如今的洪泽湖地区。
建安元年（196）春天，就在曹操把献帝接到许县的时候，刘备率关羽等南下迎击袁术，让张飞留守下邳。曹操听说刘备和袁术开战，对刘备给予了支持，以朝廷的名义任命刘备为平东将军，封宜城亭侯。曹操这么做是拉住刘备，坚定刘备与袁术斗争的信心。尽管刘备收容吕布让曹操不快，但为大局着眼，曹操还是把刘备当成自己人。对曹操来说，夺取徐州是上策，不战而把徐州由敌人转化为友军也是可以接受的。
刘备已经取得了徐州刺史的职务，但他还没有新的军职，刘备的上一个军职是公孙瓒授予的别部司马，平东将军在杂号将军之上，相当于军区或兵团司令，刘备的军职一下子升了好多级。张飞此时的军职仍然是司马，在下邳城比他职务高的有曹豹，他是下邳国相，相当于郡太守。还有陶谦的旧部许耽，职务是中郎将，也比张飞高得多。
这样势必会产生矛盾，张飞是刘备的亲信，是后方的实际负责人，但职务却不高，更重要的是，刘备率嫡系南下后，下邳城的防务以陶谦的旧部为主，很容易出问题。张飞是一员猛将，打仗比较在行，但处理复杂微妙的局面可能不拿手。如果刘备此去很快获胜，徐州倒不会出现大的闪失，但如果打了败仗或者陷入长期僵持，那就不好说了。
而这一仗，恰恰打成了拉锯战，刘备和袁术在淮阴的石亭一带交战，双方互有胜负，形成对峙的局面。从人数上说袁术占优，但从士气上看刘备更旺。袁术挺郁闷，连名不见经传的刘备都打不过，他一定觉得自己简直没法混世界了。
有人看到了这种局面，立即意识到机会来了。
这个人是吕布，他见刘备主力南下，于是乘虚袭取了刘备的后方，曹豹偷偷迎接吕布，夺取了刘备的下邳城。吕布到了小沛，并不甘心给刘备站岗放哨，他曾偷偷地给袁术写过信，这封信里都写了些什么不详，袁术给他的回信却保存了下来，在信中袁术大大地夸奖了吕布，为拉拢吕布对抗刘备，袁术表态说愿意提供20万斛粮食给他，近年来除了兵荒还有天灾，粮食稀缺，吕布在兖州被曹操打败，一个重要的原因就是缺粮，吕布深知没饭吃是什么滋味，20万斛粮食对吕布来说是一个巨大的诱惑。
吕布也想干，袁术也想干，双方一拍即合，就干了。除此之外，想干的还有上面提到的曹豹，作为陶谦的旧部，刘备到徐州以后心情有些郁闷，和张飞之间又有些矛盾，所以也想干一回，曹豹也派人秘密联络了吕布。
吕布接到袁术的信很激动，又有曹豹主动投靠，愿意充当内应，就更不多想了，立即引兵由小沛杀往下邳，负责下邳城防务的中郎将许耽派一个叫章诳的司马来见吕布，报告了下邳城里的最新情况。
吕布这才得知下邳城发生了重大变化，张飞把曹豹杀了，城中已经大乱。章诳告诉吕布城里现在人心惶惶，大家互不信任，张飞根本控制不住局面。丹阳兵有1000人屯驻在下邳城的西门，听说吕将军要来大家都特别高兴，好像看到了生的希望，章诳建议吕布引兵向西门，丹阳兵自会开门相迎。
吕布于是连夜进兵，于清晨时分来到下邳城下，丹阳兵果然打开西门，吕布进城。吕布把临时指挥所设在下邳城西门城楼上，在这里指挥手下人马和丹阳兵四处放火，大破张飞。
张飞逃出城，刘备的妻子甘氏以及刘备手下将士们的家眷，还有大量军用物资都落入吕布手中，吕布没费多大的代价就抄了刘备的老巢，夺取了下邳城。
在前线作战的刘备听到后方有变，如雷轰顶，顾不上袁术，立即回师。刘备手下将士知道家里出了事，眷属们都在吕布手里，心里面已经大乱。刘备看到这样子回下邳根本没有战胜吕布的希望，只好带着人马再次南下，试图寻求与袁术决战，但被击溃。
前后都有强敌，刘备陷入绝境。今江苏省灌南县在东汉属徐州刺史部广陵郡的海西县，现在它是个内陆县，东边还有响水等县，而在东汉，响水县和滨海县一带数千万平方公里的土地尚不存在，这里是一片大海，海西县是个典型的滨海县。在群雄争霸战中，这里并不是各路军阀争抢的要地，虽然经济比较落后，但还算安宁。
建安元年（196）秋天，这里突然来了一干人马，顿时制造出紧张的气氛。这支人马有数千人，像是在别的地方打了败仗退到这里的，人不齐、马不整，还有许多伤兵，士气十分低落。海西是个小县，一下子涌来了这么多人，吃饭都成了问题。这就是刘备率领的残兵败将。刘备一行来到这里，没吃的没喝的，不知道该往哪里去，饿极了，甚至发生了人吃人的惨剧。
落到现在这个局面，刘备怪不了别人，要怪只能怪自己，他十分懊悔。但是后悔是没有用的，现在要考虑的是怎么办，不说下一步如何翻身，就说如何解决这几千人的吃饭问题，都够难的。没有吃的，缺少粮食，几天还能克服，时间再长，人马就得一哄而散。
在这个最艰难的时刻，随军出征的徐州别驾麋竺给了刘备以最大支持。麋竺是亿万富豪，家底很厚，麋竺和兄弟麋芳散尽家财支持刘备，同时集合了仆人、宾客和族人共2000多人加入到刘备的队伍中。甘夫人落入吕布手中，生死不详，麋竺把自己的妹妹嫁给刘备当夫人。
麋竺是汉末商人从政的成功代表，在刘备事业最低谷时倾全力支持，看得出他不仅会理财，还很有政治头脑。在麋氏兄弟的大力支持下，刘备暂时可以不用下海当渔民了，但前途仍然黯淡。
走投无路之下，刘备做出了一个让人不可思议的决定，他要向吕布投降。换成袁绍或袁术，事业从巅峰一下子落入低谷，肯定会一蹶不振，说不定直接气得吐血而死，让他们弯下腰来向对手低头，那怎么可能？这种事只有吕布能做出来，因为他的脸皮厚，面子也不值钱。
刘备也能做出来，因为他没有别的办法。刘备率领手下的人马重新北上，来到下邳城外，让人报告吕布说，他想投降吕布。吕布刚进入下邳城，当了徐州刺史，听说刘备回来了，有些吃惊。听说刘备要投降自己，吕布更吃惊了。
但是，刘备的心思别人不好懂吕布却能读懂，吕布和刘备都出身于草根，都在底层奋斗挣扎过，知道人生冷暖、眉眼高低，遇到困境身上也都有惊人的忍耐力。吕布想起自己走投无路来投奔刘备的情景，有些感同身受，所以刘备请降别人不理解，他完全理解。
吕布手下有人反对，他们提醒吕布：“刘备这个人反复无常，很难加以笼络，必须早点结果他！”说这个话的人，不知想没想过吕布听到这样的话会多心，这话简直就是在骂他们的领导吕布，要说反复无常，刘备比吕布差得远。
吕布没有接受手下人的意见，还把这些话告诉了刘备。刘备听完心里不安，他现在只想自保，别无他图，于是请人出面到吕布那里说情。刘备请的是谁史书没有记载，不会是关羽等人，最有资格为他说话的人是孔融，如果孔融出面，吕布应该给个面子，还有许劭、陈登、陈群这些人，刘备对他们都很尊重，现在他们是吕布的座上客，请他们去说和一定不难。
为了打消吕布的顾虑，刘备让人带话给吕布，只要接受他投降，他愿意去小沛。这正符合吕布的想法，于是答应了刘备的请求。
吕布收留刘备也是一个错误，他的错误跟当初刘备一样。
但是把徐州整个形势进行了一番梳理后，吕布也发现自己的力量并不强大，四周的形势仍然险恶，与其跟刘备拼命，不如把他收编。不久前吕布内部发生了一次叛乱，差点儿要了他的命。防曹操、防袁绍，还得防袁术，防徐州地方实力派和内部的叛徒，从里到外吕布都得提防，这是他不能再与刘备血拼到底的原因。
吕布归还了刘备的妻子，古文中的“妻子”通常指的是妻子和儿女，但这里仅指妻子，因为刘备的第一个儿子尚未出生，史书也没有刘备有女儿的记载，这个“妻子”指的是甘氏。
吕布命令刘备回豫州，和自己一道抵抗袁术。史书上的这条记载一下子让人摸不着头脑，曹操、袁绍才是吕布当前主要的敌人，刘备到小沛的主要任务应该是对付他们，而且小沛的位置也不对，如果抵抗袁术，应该把刘备派到徐州南部才对。但这不是史书记载的错误，结合郝萌反叛事件对此就容易理解了。吕布这时已洞悉了袁术的居心，他们翻脸是迟早的事，所以已经把袁术当成了敌人，至于曹操，吕布正考虑如何与他消除之前的恩怨化敌为友。这段时间以来，袁绍、袁术、曹操、吕布、刘备等人一会儿是敌，一会儿是友，变化很快，让史学家们都凌乱了。
吕布按照刺史的规格为刘备准备了车马和仆役，在泗水河上举行了发还将士家眷的仪式，为刘备第二次担任豫州刺史饯行。对刘备来说，虽然面子不好看，但最难的一关总算过去了，张飞也回归了队伍。刘备率关羽、张飞等人再次来到小沛，这次待的时间比上一回要长得多。
听说刘备没被消灭，还去了小沛当上了豫州刺史，袁术不干了。
袁术派纪灵率三万人马攻打刘备，刘备刚到小沛，手下充其量也就几千人，面对几乎十倍于己的敌人，刘备自知不敌，赶紧向吕布求援。接到刘备的请求，吕布手下众将都建议不要管这件事。
吕布不同意这么做，他的眼光更宏观：“袁术如果消灭刘备，那就会北连泰山诸将，我就被袁术包围在其中，没什么前途出路了，刘备不得不救！”
刘备在徐州时泰山帮的臧霸、昌豨等人还跑出来打个照面，表面上服从，吕布当上徐州刺史后，这些人连面都不照了。前不久，吕布为扩大控制范围，想进攻琅邪国相萧建，给萧建写了封信，萧建畏惧吕布，派人带上礼物来见吕布，但吕布还是想把琅邪国收归自己管理，于是亲自率兵赶到了琅邪国。
吕布的举动引起了臧霸的疑虑，臧霸和吕布开战。战斗中，臧霸所部使用了毒箭，射中吕布手下不少人马，吕布不能取胜，退回下邳。不过后来臧霸还是服软，表示愿意接受吕布的指挥，但进攻琅邪国一事也就不了了之。
吕布担心的是，刘备一旦被消灭，袁术将与臧霸等人联手，自己就处在袁术的包围之中了。所以，吕布决定亲自去帮刘备解围，但带去的人马并不多，只有1000名步兵和200名骑兵。
纪灵听说吕布来了，于是停止了对小沛的进攻。吕布率部在小沛城西南方向扎营，之后发出请帖，宴请纪灵。宴席上，吕布对纪灵说：“刘玄德是我兄弟，他现在被诸君围困，所以我来救他。我生性不喜欢跟人斗，只喜欢替人和解。”
吕布命人在营门外立上一支戟，对众人说：“诸君请看，戟上有一小枝，我要一箭射中，诸君应当和解，不能再争斗；如果射不中，你们再斗我不管。”戟的头部是一个不对称的十字形，用来横击的一端刃部长而尖，为主刃，另一端与主刃垂直，短而粗，称小枝。吕布举弓射戟，正中小枝，众人皆惊，齐呼：“将军天威也！”
第二天吕布再请大家喝酒，纪灵随后率军撤退。