就在曹操準備向呂布動手時，呂布那邊的形勢也發生了變化。
這兩年，劉備一直駐守在小沛，但他並不甘心給呂布當盾牌，劉備趁著別人都在忙活的時候，自己一直悄悄埋頭擴充勢力，他對外宣稱只有幾千人馬，其實至少發展到了萬人以上。
這還不是最讓呂布擔心的，據情報說，劉備私下裡跟袁紹和曹操來往密切，當時袁紹和曹操的關係已經由微妙轉為緊張，但劉備跟他們都保持著來往，劉備給袁紹秘密寫信，又派人到許縣跟曹操拉關係。
這些情況很快得到了證實，獻帝的詔書下達，把劉備之前的平東將軍升為鎮東將軍，這個職務此前是一直由曹操擔任，說明曹操對劉備很看重，當然也是對呂布的牽制。呂布和劉備之間雖然沒有明確的上下級關係，但小沛是呂布讓給劉備的，豫州刺史也是呂布讓的，劉備的架勢是想撇開呂布獨立發展，這讓呂布極為不快。但僅就這一點還不能跟劉備翻臉，因為這等於給曹操難看，呂布現在需要曹操的支持。
可是，隨後又發生了更讓呂布不爽的事。在討伐袁術時被呂布臨陣策反的韓暹、楊奉二人自恃有功，在呂布的地盤上總鬧事，為了打發他們，呂布讓二人向豫州、兗州和青州方向發展，打下地盤都歸他們。這二位便率領部下離開了徐州一路向北連殺帶搶，激起了不少民憤。搶著搶著，就到了劉備的地盤上。劉備原來只駐紮在小沛，但近來已經悄悄地把手伸得很長，不僅豫州刺史部沛國北部幾乎盡歸其所有，而且還伸向了相鄰的地區，韓暹和楊奉大概沒打聽清楚，或者明知是劉備但沒把他放在眼裡，所以來到這裡照搶不誤。
劉備沒去找呂佈告狀，他想自己解決。劉備假意約楊奉相見，楊奉還以為請他喝酒，就去了，結果讓劉備抓了起來。劉備用楊奉作人質很快瓦解了楊奉的人馬，韓暹失去楊奉的支援成為孤軍，他想帶著殘餘武裝回并州老家，結果走到一個叫杼秋的地方，被當地一個叫張宣的屯帥所殺。
有組織有紀律叫團隊，有組織沒紀律只能叫團伙。
劉備沒費太大損失就解決了韓暹和楊奉，得到了很大實惠，為了給呂佈一個交代，劉備主動給呂布寫了封信，信中對呂布說白波賊頭領韓暹、楊奉二人流竄至豫州，沿途燒殺搶掠，民憤極大，更為可氣的是，他們幹了那麼多壞事，還打著您的旗號，說是您讓他們幹的，這是公然對您的造謠污蔑，為此我就把他們收拾了，既為民除害，又幫您洗刷了清白。得了便宜沒啥，還要賣乖，就可氣了。
這件事還沒完，又發生了一件事，更氣人。建安三年（198）春天，呂布派人到河內郡一帶買馬，呂布擅長騎兵作戰，但兗州、徐州一帶不產良馬，無法在當地補充，他只有派人到外地買馬。呂布派去買馬的人回來時路過劉備的防區，結果讓人搶了。
在呂布看來，這件事不用動腦子就知道是誰幹的，敢搶飛將軍的馬，只有劉備有這個膽。呂布決定對劉備不再忍耐，直接懲罰。呂布命張遼和高順帶隊出征，他在下邳做後援，但戰事並不順利，劉備一不認錯，二不投降，堅守小沛，一時難以攻克。
這個時候，二人大概都會第一時間給曹操寫信，劉備是求援，呂布則解釋為什麼要收拾劉備。曹操如果接到他們二人的信，只會扔到一邊，是非曲直不重要，重要的是兩個對手自己先幹起來了。呂布親自率軍增援張遼和高順，小沛城裡的劉備有點兒吃不消了。正在這時，劉備接到報告說有一支曹軍向小沛開來，頓時感到了希望。
可能在劉備看來，曹操一定會救自己，因為他剛被曹操任命為鎮東將軍就被呂布消滅了，這種「打狗不看主人」的做法如果視而不見，將會產生對曹操不利的連鎖反應。劉備的判斷是正確的，眼看劉備快要被呂布消滅，曹操決定派一支人馬過來增援他。呂布有點兒緊張，但隨後探明來的不是曹操本人，而是他的老對手、「獨目將軍」夏侯惇，而且只有幾千人，呂布才鬆口氣。呂布命高順在半道伏擊夏侯惇，夏侯惇戰敗，退回。
劉備徹底失望，趁夜突圍，小沛被攻克。劉備逃得很狼狽，只帶著關羽、張飛、趙雲以及麋竺等人和少量人馬，自己的兩位妻子甘氏和麋氏都沒來得及帶上。
建安三年（198）10月，曹操親自率大軍趕來了。
曹操行進到與沛國西面相鄰的梁國時，遇到了劉備。劉備這才見到了真正的救星，一見到曹操，就力勸他一鼓作氣殺往徐州，把呂某人徹底消滅。曹操既然出動，也不會空手而歸，他在南陽郡連輸了兩次，需要來一場勝利提振士氣。
但是如何處理劉備，曹操有些猶豫。當時勸曹操藉機殺了劉備的大有人在，比如負責兗州刺史部事務的大鬍子將軍程昱就勸他：「劉備此人有雄才，而且很會贏得民心，終究不會甘居人下，應該早點消滅他。」曹操想了想，沒同意：「方今正是收天下英雄之時，殺一個人而失天下英雄之心，不能這樣做呀！」曹操不僅接納了劉備，還以獻帝的名義正式任命劉備為豫州刺史。
對劉備而言這項任命來得太遲了，因為他已先後兩次就任該職，但對朝廷而言，做出這項任命已經算破例了。獻帝東歸以來，對這些年各地自行任命的官職一直採取不承認態度，當初曹操握有整個兗州，朝廷可以承認他的實力，拜他為鎮東將軍，但對於他希望得到的兗州牧一職，朝廷拖了很久才給。
曹操命劉備率領他的殘部隨軍行動。
對於曹操下一步的進攻重點，呂布的判斷是下邳而不是小沛，所以下令把主力快速南撤。梁國與下邳國之間隔著一個彭城國，呂布把主力分成兩部，一部分部署在下邳城周圍，一部分部署在彭城國境內。
呂布親臨前線，動員大家誓死保衛彭城。但是曹軍似乎更有信心，打起仗來也很有章法，根本不跟呂布硬拚，而是在運動中尋找戰機，曹操人多勢眾，呂布處於被動挨打的局面。
呂布產生了撤退的想法，想依托下邳城的堅固，放曹操來攻。呂布大概想，曹操不敢在徐州停留時間太長，南面的張繡、劉表，北面的袁紹，還在近旁的袁術，對曹操來說哪一個都比他重要，只要守得住，曹操必撤軍。但陳宮認為應該把防禦重心放在彭城，理由是彭城境內地勢更有利，便於同曹操大軍周旋，他建議應當改變固守挨打的局面，分出多路奇兵襲擾曹軍兩翼，尤其是他的後勤補給線，曹軍人馬數萬，拼人多是他的優勢，但後勤保障就是他的劣勢，一旦糧草供應不上，曹軍不戰而退。
應該說，陳宮是對的，呂布應該學學張繡，論名氣張繡頂多是個小字輩，因為呂布跟他叔叔張濟可以稱兄道弟，論實力張繡還不如呂布，但張繡能把曹操打敗兩次，而且敗得一次比一次慘。呂布似乎忽略了這些，忽略了張繡以弱勝強靠的是什麼，固執地認為堅守才對自己有利。呂布下令主力撤回下邳一線，彭城隨即被曹軍攻克。
撤回下邳後，呂布方面士氣十分低落。陳宮提出拒敵於外，在運動中殲敵，他認為曹操的大軍必須經過泗水，可以依托泗水河組織防線，阻擊曹軍的進攻。
呂布不同意這個看法，泗水那麼長，如何在沿線都組織起有效防線來？待敵兵渡河至一半時發起攻擊豈不更有效？大概呂布也經常研究兵法，《吳子》講到有十三種最佳的進攻狀況，敵人渡河到一半時就是其中一種。《孫子兵法》也講「敵人渡河來攻，不要在水裡跟他打，等他們渡河到河中時再攻擊」，所以呂布沒聽陳宮的建議，而是集重兵於泗水河邊曹軍必經之處，待曹軍主力渡河時先不對其發起攻擊，待其渡至一半再突然攻擊。
可是，呂布又錯了。曹軍來了，開始渡河，呂布下令攻擊，千弩怒射，萬箭齊發，曹軍紛紛中箭，有被射死的，有溺水而死的，曹軍大敗。但是所謂大勝必經大忍、大敗常因心切，呂布還沒來得及慶祝，突然接到報告說曹軍主力已經從南邊過了河，正朝下邳殺去。
呂布大驚，才知道上當了，這裡的曹軍只是誘餌，敵軍主攻方向不在這裡。兵法是一門高深的學問，相對於公認的兵法研究權威曹操，呂布只能算兵法愛好者，知其一不知其二，不如不知。
呂布趕緊下令撤軍，拚命往下邳城趕。還算好，呂布先一步進了城。喘息未定，讓呂布更鬧心的事傳來：陳登反叛了。