興平二年（195年），曹操將兗州各城全部收復，在鉅（jù）野擊敗呂布，呂布東逃投奔劉備。
呂布見到劉備後，對其非常尊敬，對劉備說，“我和閣下都是北疆邊境的人。我當時見關東軍起兵，想要誅殺董卓。但我殺了董卓東出，關東諸將卻沒有一個接納我，都想要殺了我。”
並請劉備坐在帳中的牀上，令妻妾向劉備行禮，酌酒飲食，稱劉備爲賢弟。
劉備的部將沒有不橫目呂布的。
劉備見呂布語言無常，表面上一派無所謂的樣子，但，心裡卻不開心。
…… ……
興平二年（195年），袁術率軍攻打徐州，與劉備相持於盱眙（xūyí）、淮陰。相持一個月，雙方互有勝敗。
袁術給呂布寫了一封信，箭射到城樓上，誘使他襲擊下邳（pī），許諾事成之後，給他二十萬斛大米。
於是，見利忘義的呂布，水陸東下，軍隊抵達下邳西四十里時，劉備的中郎將丹楊人許耽派司馬章誑前來迎接呂布，並向呂布透露了張飛和曹豹相爭，下邳城內大亂，丹陽兵都在西白門城內等待呂布的到來，於是呂布便大舉進軍，早晨到達城下。
天亮後，丹陽兵打開城門，呂布坐在城門上，指揮軍隊大破張飛，俘虜劉備的妻妾兒女及其部曲的家眷。
…… ……
此時，劉備爲袁術所敗逃往海西，飢餓疲憊，向呂布請求投降。
呂布又惱火袁術答應給的大米，不夠數，就不再幫袁術，而準備了車馬迎接劉備，讓劉備擔任豫州刺史，派他駐守小沛。
呂布自稱爲徐州牧。
同年七月，因李榷（què）、郭汜（sì）的火拼，漢獻帝從長安東歸，途徑河東，下詔書令呂布迎駕。由於呂布的軍隊沒有儲備足夠的糧食，無法勤王，於是呂布派遣使者上書謝罪。朝廷任命呂布爲平東將軍，封平陶侯。
建安元年（196年），袁術派大將紀靈帶領步騎共三萬多人馬征討劉備，劉備向呂布求援。手下將領對呂布說，“將軍您一直想除掉劉備，如今可借袁術的手除掉他。”
呂布說，“並非如此，袁術如果佔據了小沛，就會聯合北面泰山一帶的部隊，我們就會被袁術所包圍，我不能不去救劉備啊。”
於是領步兵千人、騎兵二百，飛速趕往小沛。
紀靈等人聽說呂布前來援救劉備，只好收兵，不敢輕舉妄動。
…… ……
呂布在離小沛西南一里的地方紮下營寨，派衛士去請紀靈等將領來他的營寨飲酒，紀靈等人也回請呂布一起飲酒。
呂布對紀靈等人說，“玄德，是我呂布的賢弟。如今他被諸位所圍，我特意趕來救他。我呂布生性不愛看別人互相爭鬥，只喜歡替別人解除紛爭。”
呂布命門候在營門中豎起一支戟，說，“諸位看我射戟上的小支，如一發射中，諸君當立即停止進攻，離開這裡，如射不中，那你們就留下與劉備決一死戰。”
他引弓向戟射出一箭，正好中了小支。
諸將大爲震驚，誇讚說，“將軍您真是有天神般的威力呀！”
第二天，呂布又與諸將歡會宴飲，然後各自回兵。
這就是著名“轅門射戟”的故事，被地方戲曲都演爛了的橋段。
這只是表現呂布的武功、箭法。
建安元年（196年）六月，夜半時，呂布部將河內人郝萌在袁術的慫恿下發動叛亂，率兵攻打呂布治所下邳，城池防守堅固無法攻入，呂布不知道造反的是誰，帶領家眷逃往高順營寨，高順問道，“將軍知道是誰來攻打你嗎？”
呂布回答說，“不知道，只聽到是河內人的聲音。”
高順便猜到造反的是郝萌，於是率部到下邳平叛，弓弩齊發射殺郝萌軍，天亮還營（《冊府元龜》則記載呂布與高順一同前往平叛）。
郝萌的部將曹性反正，與郝萌對戰，郝萌刺傷曹性，曹性斬斷郝萌一臂，高順乘勢斬下郝萌的首級，用牀擔着受傷的曹性前往見呂布。
呂布問曹性此事起源，曹性回答，“郝萌受到袁術的鼓動而造反。”
呂布又問，“同謀的都有誰？”
曹性回答說陳宮同謀，當時陳宮坐在呂布旁白，臉發紅，旁人都察覺到了。
呂布因爲陳宮是大將，沒有追究。
曹性又說，“郝萌造反時曾問我可行嗎？我說呂大將軍神勇不可對抗，沒想到郝萌狂惑不止。”
呂布對曹性說，“你真是個健兒。”
讓其好好養傷，等曹性傷愈後，讓他統領郝萌的餘部。
…… ……
袁術冒出稱帝的念頭後，就想聯合呂布，使他爲自己所用，於是向呂布提出讓他的兒子娶呂布之女爲妻，呂布同意了。
袁術派韓胤爲使節，向呂布正式轉達他將更換年號、登基稱帝的事情，同時請求接呂布的女兒與自己的兒子去完婚。
沛相陳珪擔心袁術、呂布成了親家，徐州、揚州聯爲一體，將會危害國家，於是前往遊說呂布，對呂布說，“曹公奉迎天子，輔佐朝政，征討八方，威震四海，而將軍您應與他合作，以取得天下安寧。如果您與袁術成了親家，將會擔上不義之人的罪名，那樣形勢就對您不利了。”
呂布心裡也怨恨當初袁術不接納自己，雖說女兒此時已經隨韓胤走了，他還是把她追了回來，拒絕了這門親事，並將使者韓胤戴上枷鎖、鐐銬，送往許都街市上斬首示衆。
陳珪想派其子陳登到許都，說明呂布願意與曹操合作，呂布不同意。
正巧曹操的使者這時來到，傳漢獻帝的旨意，任命呂布爲左將軍。
呂布大喜，於是讓陳登啓程，還命他帶着書信，向漢獻帝謝恩。
陳登拜謁曹操，述說了呂布有勇無謀、反覆無常的缺點，希望曹操早日除掉他。曹操說，“呂布是個具有狼子野心的人，實在不能讓他久留世上，你當然是最熟悉內情的。”
當即把陳珪的年俸祿提到二千石，任命陳登爲廣陵太守。
臨別時，曹操拉着陳登的手說，“東邊的事，便全託付給你了。”
囑咐陳登暗地裡分化呂布的隊伍，爲自己做內應。