劉備入主徐州惹怒了一個人，袁術。
聽說劉備取代陶謙當了徐州刺史，並一改與自己結盟的現狀轉投袁紹，這讓袁術無法釋懷。袁術一向心高氣傲，本來就瞧不起劉備，他曾對人說：「我袁術生平還從來沒有聽說過天下還有劉備這個人！」
袁術說幹就幹，率兵揮師北上，直取徐州。劉備不敢怠慢，趕緊整頓人馬南下迎擊，雙方在徐州刺史部南部的下邳國、廣陵郡一帶交戰，這裡就是如今的洪澤湖地區。
建安元年（196）春天，就在曹操把獻帝接到許縣的時候，劉備率關羽等南下迎擊袁術，讓張飛留守下邳。曹操聽說劉備和袁術開戰，對劉備給予了支持，以朝廷的名義任命劉備為平東將軍，封宜城亭侯。曹操這麼做是拉住劉備，堅定劉備與袁術鬥爭的信心。儘管劉備收容呂布讓曹操不快，但為大局著眼，曹操還是把劉備當成自己人。對曹操來說，奪取徐州是上策，不戰而把徐州由敵人轉化為友軍也是可以接受的。
劉備已經取得了徐州刺史的職務，但他還沒有新的軍職，劉備的上一個軍職是公孫瓚授予的別部司馬，平東將軍在雜號將軍之上，相當於軍區或兵團司令，劉備的軍職一下子升了好多級。張飛此時的軍職仍然是司馬，在下邳城比他職務高的有曹豹，他是下邳國相，相當於郡太守。還有陶謙的舊部許耽，職務是中郎將，也比張飛高得多。
這樣勢必會產生矛盾，張飛是劉備的親信，是後方的實際負責人，但職務卻不高，更重要的是，劉備率嫡系南下後，下邳城的防務以陶謙的舊部為主，很容易出問題。張飛是一員猛將，打仗比較在行，但處理複雜微妙的局面可能不拿手。如果劉備此去很快獲勝，徐州倒不會出現大的閃失，但如果打了敗仗或者陷入長期僵持，那就不好說了。
而這一仗，恰恰打成了拉鋸戰，劉備和袁術在淮陰的石亭一帶交戰，雙方互有勝負，形成對峙的局面。從人數上說袁術佔優，但從士氣上看劉備更旺。袁術挺鬱悶，連名不見經傳的劉備都打不過，他一定覺得自己簡直沒法混世界了。
有人看到了這種局面，立即意識到機會來了。
這個人是呂布，他見劉備主力南下，於是乘虛襲取了劉備的後方，曹豹偷偷迎接呂布，奪取了劉備的下邳城。呂布到了小沛，並不甘心給劉備站崗放哨，他曾偷偷地給袁術寫過信，這封信裡都寫了些什麼不詳，袁術給他的回信卻保存了下來，在信中袁術大大地誇獎了呂布，為拉攏呂布對抗劉備，袁術表態說願意提供20萬斛糧食給他，近年來除了兵荒還有天災，糧食稀缺，呂布在兗州被曹操打敗，一個重要的原因就是缺糧，呂布深知沒飯吃是什麼滋味，20萬斛糧食對呂布來說是一個巨大的誘惑。
呂布也想幹，袁術也想幹，雙方一拍即合，就干了。除此之外，想幹的還有上面提到的曹豹，作為陶謙的舊部，劉備到徐州以後心情有些鬱悶，和張飛之間又有些矛盾，所以也想幹一回，曹豹也派人秘密聯絡了呂布。
呂布接到袁術的信很激動，又有曹豹主動投靠，願意充當內應，就更不多想了，立即引兵由小沛殺往下邳，負責下邳城防務的中郎將許耽派一個叫章誑的司馬來見呂布，報告了下邳城裡的最新情況。
呂布這才得知下邳城發生了重大變化，張飛把曹豹殺了，城中已經大亂。章誑告訴呂布城裡現在人心惶惶，大家互不信任，張飛根本控制不住局面。丹陽兵有1000人屯駐在下邳城的西門，聽說呂將軍要來大家都特別高興，好像看到了生的希望，章誑建議呂布引兵向西門，丹陽兵自會開門相迎。
呂佈於是連夜進兵，於清晨時分來到下邳城下，丹陽兵果然打開西門，呂布進城。呂布把臨時指揮所設在下邳城西門城樓上，在這裡指揮手下人馬和丹陽兵四處放火，大破張飛。
張飛逃出城，劉備的妻子甘氏以及劉備手下將士們的家眷，還有大量軍用物資都落入呂布手中，呂布沒費多大的代價就抄了劉備的老巢，奪取了下邳城。
在前線作戰的劉備聽到後方有變，如雷轟頂，顧不上袁術，立即回師。劉備手下將士知道家裡出了事，眷屬們都在呂布手裡，心裡面已經大亂。劉備看到這樣子回下邳根本沒有戰勝呂布的希望，只好帶著人馬再次南下，試圖尋求與袁術決戰，但被擊潰。
前後都有強敵，劉備陷入絕境。今江蘇省灌南縣在東漢屬徐州刺史部廣陵郡的海西縣，現在它是個內陸縣，東邊還有響水等縣，而在東漢，響水縣和濱海縣一帶數千萬平方公里的土地尚不存在，這裡是一片大海，海西縣是個典型的濱海縣。在群雄爭霸戰中，這裡並不是各路軍閥爭搶的要地，雖然經濟比較落後，但還算安寧。
建安元年（196）秋天，這裡突然來了一干人馬，頓時製造出緊張的氣氛。這支人馬有數千人，像是在別的地方打了敗仗退到這裡的，人不齊、馬不整，還有許多傷兵，士氣十分低落。海西是個小縣，一下子湧來了這麼多人，吃飯都成了問題。這就是劉備率領的殘兵敗將。劉備一行來到這裡，沒吃的沒喝的，不知道該往哪裡去，餓極了，甚至發生了人吃人的慘劇。
落到現在這個局面，劉備怪不了別人，要怪只能怪自己，他十分懊悔。但是後悔是沒有用的，現在要考慮的是怎麼辦，不說下一步如何翻身，就說如何解決這幾千人的吃飯問題，都夠難的。沒有吃的，缺少糧食，幾天還能克服，時間再長，人馬就得一哄而散。
在這個最艱難的時刻，隨軍出征的徐州別駕麋竺給了劉備以最大支持。麋竺是億萬富豪，家底很厚，麋竺和兄弟麋芳散盡家財支持劉備，同時集合了僕人、賓客和族人共2000多人加入到劉備的隊伍中。甘夫人落入呂布手中，生死不詳，麋竺把自己的妹妹嫁給劉備當夫人。
麋竺是漢末商人從政的成功代表，在劉備事業最低谷時傾全力支持，看得出他不僅會理財，還很有政治頭腦。在麋氏兄弟的大力支持下，劉備暫時可以不用下海當漁民了，但前途仍然黯淡。
走投無路之下，劉備做出了一個讓人不可思議的決定，他要向呂布投降。換成袁紹或袁術，事業從巔峰一下子落入低谷，肯定會一蹶不振，說不定直接氣得吐血而死，讓他們彎下腰來向對手低頭，那怎麼可能？這種事只有呂布能做出來，因為他的臉皮厚，面子也不值錢。
劉備也能做出來，因為他沒有別的辦法。劉備率領手下的人馬重新北上，來到下邳城外，讓人報告呂布說，他想投降呂布。呂布剛進入下邳城，當了徐州刺史，聽說劉備回來了，有些吃驚。聽說劉備要投降自己，呂布更吃驚了。
但是，劉備的心思別人不好懂呂布卻能讀懂，呂布和劉備都出身於草根，都在底層奮鬥掙扎過，知道人生冷暖、眉眼高低，遇到困境身上也都有驚人的忍耐力。呂布想起自己走投無路來投奔劉備的情景，有些感同身受，所以劉備請降別人不理解，他完全理解。
呂布手下有人反對，他們提醒呂布：「劉備這個人反覆無常，很難加以籠絡，必須早點結果他！」說這個話的人，不知想沒想過呂布聽到這樣的話會多心，這話簡直就是在罵他們的領導呂布，要說反覆無常，劉備比呂布差得遠。
呂布沒有接受手下人的意見，還把這些話告訴了劉備。劉備聽完心裡不安，他現在只想自保，別無他圖，於是請人出面到呂布那裡說情。劉備請的是誰史書沒有記載，不會是關羽等人，最有資格為他說話的人是孔融，如果孔融出面，呂布應該給個面子，還有許劭、陳登、陳群這些人，劉備對他們都很尊重，現在他們是呂布的座上客，請他們去說和一定不難。
為了打消呂布的顧慮，劉備讓人帶話給呂布，只要接受他投降，他願意去小沛。這正符合呂布的想法，於是答應了劉備的請求。
呂布收留劉備也是一個錯誤，他的錯誤跟當初劉備一樣。
但是把徐州整個形勢進行了一番梳理後，呂布也發現自己的力量並不強大，四周的形勢仍然險惡，與其跟劉備拚命，不如把他收編。不久前呂布內部發生了一次叛亂，差點兒要了他的命。防曹操、防袁紹，還得防袁術，防徐州地方實力派和內部的叛徒，從裡到外呂布都得提防，這是他不能再與劉備血拼到底的原因。
呂布歸還了劉備的妻子，古文中的「妻子」通常指的是妻子和兒女，但這裡僅指妻子，因為劉備的第一個兒子尚未出生，史書也沒有劉備有女兒的記載，這個「妻子」指的是甘氏。
呂布命令劉備回豫州，和自己一道抵抗袁術。史書上的這條記載一下子讓人摸不著頭腦，曹操、袁紹才是呂布當前主要的敵人，劉備到小沛的主要任務應該是對付他們，而且小沛的位置也不對，如果抵抗袁術，應該把劉備派到徐州南部才對。但這不是史書記載的錯誤，結合郝萌反叛事件對此就容易理解了。呂布這時已洞悉了袁術的居心，他們翻臉是遲早的事，所以已經把袁術當成了敵人，至於曹操，呂布正考慮如何與他消除之前的恩怨化敵為友。這段時間以來，袁紹、袁術、曹操、呂布、劉備等人一會兒是敵，一會兒是友，變化很快，讓史學家們都凌亂了。
呂布按照刺史的規格為劉備準備了車馬和僕役，在泗水河上舉行了發還將士家眷的儀式，為劉備第二次擔任豫州刺史餞行。對劉備來說，雖然面子不好看，但最難的一關總算過去了，張飛也回歸了隊伍。劉備率關羽、張飛等人再次來到小沛，這次待的時間比上一回要長得多。
聽說劉備沒被消滅，還去了小沛當上了豫州刺史，袁術不幹了。
袁術派紀靈率三萬人馬攻打劉備，劉備剛到小沛，手下充其量也就幾千人，面對幾乎十倍於己的敵人，劉備自知不敵，趕緊向呂布求援。接到劉備的請求，呂布手下眾將都建議不要管這件事。
呂布不同意這麼做，他的眼光更宏觀：「袁術如果消滅劉備，那就會北連泰山諸將，我就被袁術包圍在其中，沒什麼前途出路了，劉備不得不救！」
劉備在徐州時泰山幫的臧霸、昌豨等人還跑出來打個照面，表面上服從，呂布當上徐州刺史後，這些人連面都不照了。前不久，呂布為擴大控制範圍，想進攻琅邪國相蕭建，給蕭建寫了封信，蕭建畏懼呂布，派人帶上禮物來見呂布，但呂布還是想把琅邪國收歸自己管理，於是親自率兵趕到了琅邪國。
呂布的舉動引起了臧霸的疑慮，臧霸和呂布開戰。戰鬥中，臧霸所部使用了毒箭，射中呂布手下不少人馬，呂布不能取勝，退回下邳。不過後來臧霸還是服軟，表示願意接受呂布的指揮，但進攻琅邪國一事也就不了了之。
呂布擔心的是，劉備一旦被消滅，袁術將與臧霸等人聯手，自己就處在袁術的包圍之中了。所以，呂布決定親自去幫劉備解圍，但帶去的人馬並不多，只有1000名步兵和200名騎兵。
紀靈聽說呂布來了，於是停止了對小沛的進攻。呂布率部在小沛城西南方向紮營，之後發出請帖，宴請紀靈。宴席上，呂布對紀靈說：「劉玄德是我兄弟，他現在被諸君圍困，所以我來救他。我生性不喜歡跟人鬥，只喜歡替人和解。」
呂布命人在營門外立上一支戟，對眾人說：「諸君請看，戟上有一小枝，我要一箭射中，諸君應當和解，不能再爭鬥；如果射不中，你們再鬥我不管。」戟的頭部是一個不對稱的十字形，用來橫擊的一端刃部長而尖，為主刃，另一端與主刃垂直，短而粗，稱小枝。呂布舉弓射戟，正中小枝，眾人皆驚，齊呼：「將軍天威也！」
第二天呂布再請大家喝酒，紀靈隨後率軍撤退。