吕布战败后逃出长安城，这时身边仅剩下百余名骑兵，可谓是非常的落魄。吕布遥望长安都城，心中有无限的感慨，那里是他曾经辉煌过的地方，如今自己举目无亲，何处才是自己的容身之所啊！
但吕布好歹也是经过大风浪的人，留得青山在，哪怕没柴烧呢？失败只是暂时的，只要以后肯努力，一定会有东山再起的机会。于是吕布收拾心情，重新振作了起来，打算先找个地方安顿下来再做打算。吕布首先想到的就是袁术。
袁术在当时是实力最强大的诸侯之一，手下部卒有十几万，坐拥几郡之地，可谓是兵多将广。但是袁术并没有收容吕布，原因是吕布自恃有功而骄傲自大，而且还纵容手下沿路抢掠百姓，因此引起了袁术的不满。
吕布心想此处不留爷，自有留爷处。于是又到河北去投靠袁绍，一开始袁绍倒是很欢迎吕布，对他礼遇有加。在袁绍这里，二人联手共同讨伐黑山贼张燕。当地的黑山军有一万多精兵，还有几千的骑兵，实力强大。
吕布经常骑着赤兔马，带着和自己关系比较好的成廉、魏越等人和十几名亲信骑马冲击张燕的军阵，有时候一天往来三四趟，每次都能砍了一些黑山军的首级回来，把张燕气的可是不轻，可是张燕也知道吕布勇猛，面对他的骚扰是一点办法都没有。这样连续作战了十几天，终于打败了张燕。
这时候吕布骄傲自大的毛病又犯了，自认为讨贼有功，要求袁绍给自己增加军队，袁绍当然不答应了，开玩笑，你吕布是什么样的人我又不是不知道，那可是出了名的白眼狼啊！给你增加军队不是等于给自己脖子上放刀子吗！
吕布手下的将士呢，可能是之前跟着董卓烧杀抢掠习惯了，臭毛病始终没改，经常的抢劫、掠夺财物，袁绍因此开始忌恨吕布。吕布也因此而感到不安，便向袁绍提出要回洛阳去，袁绍一听他要走，当然同意了，于是以天子的名义任命吕布为司隶校尉，并派了甲士护送吕布，实际上是打算找机会要杀掉他。
吕布也怀疑袁绍在打自己的主意，多留了个心眼，使了一招空城计。这天吕布找人在自己的营帐中弹琴，自己则悄悄的溜走了，到了深夜，甲士们开始行动，拿着刀对吕布的床上那是一顿乱砍啊，砍完就认为吕布已经死了，于是回去向袁绍复命。到了第二天，袁绍却得知吕布居然还活着，就下令关闭城门，怕的是吕布趁机回来报复。
这时候吕布已经到了河内，受到了太守张杨的热烈欢迎，二人随即联合一处。袁绍非常忌惮吕布，担心他会对自己不利，便派了一支军队去追杀吕布，可是这些士兵都害怕吕布，即使追上了，也没人敢靠近他，只能眼睁睁的看着他离开。
吕布途径陈留时，张邈得知他的到来，非常高兴，就派人前去迎接，并好好的款待了他一番，临分手时二人紧握着双手不忍分别，并发誓从此结为同盟，祸福相依，生死与共。
兴平元年（公元194年），曹操率军东征徐州陶谦，派手下将领陈宫驻守东郡。陈宫却趁机劝说张邈起兵，而且陈宫认为吕布勇猛无敌，就让张邈迎接吕布前来一起占据兖州，以观天下形势，待时起兵，与群雄争锋。张邈听从了陈宫的建议，和弟弟张超以及陈宫等人，一起迎接吕布担任兖州牧，并率兵占据了濮阳，得到了兖州郡县的响应。看着自己的战斗成果，吕布这个高兴啊，心想，自己终于东山再起了。要说陈宫好歹也是当时小有名气的谋士，文武全才的人物，也不知道怎么想的，居然会看上吕布这样的人，甘愿受他驱策。
可是吕布并没有高兴太久，正在徐州和陶谦对峙的曹操得知消息后被吓了一跳，要知道，兖州可是曹操的大本营啊，一旦失去了兖州，对当时曹操的打击无疑是巨大的，曹操怎么能不着急呢？于是曹操什么都不管了，赶紧率领军队回援兖州。
濮阳城中有一个大姓田氏，那可是曹操的铁杆粉丝，忠实的拥护者，得知曹操回来后，便在城中响应曹操。曹操趁机率兵入城，下令烧毁东城门，以此激励手下将士与吕布决一死战，吕布则下令骑兵先冲散青州军队，导致曹操阵势大乱，曹操被吕布手下的士兵抓住，可是吕布的士兵不认识曹操啊，就问他曹操在哪？
曹操心里还纳闷呢：“我就是曹操啊，怎么他们还问我在哪里呢？哦，明白了，他们还不知道我就是曹操，我可不能承认。”就告诉他们骑黄马的就是曹操，于是吕布就带人去追击骑黄马的人而放了曹操。曹操暗叫一声好险，策马冒着浓烟冲了出去，因此还被烧伤了左手。
在这之后双方数次交战，各有输赢，相持了有一百多天，这时，天气大旱，又闹起了蝗灾，出现了饥荒，并发生了人吃人的现象，吕布便将部队转移到山阳驻扎。
兴平二年（公元195年），吕布再次率兵从东缗出发，和陈宫一起率领一万兵士攻打曹操。此时曹操部下的士兵全都派出去割麦子去了，在营中的只有一千来人，这点人根本守不住营寨。怎么办呢？曹操就下令让城中的妇人全都到矮墙里守御，营中的这一千多士兵全部都在营垒边上摆出一副无所畏惧的样子。曹操营寨的西边是一条大堤，南边有一边茂密的树林。吕布见了，就怀疑曹操有伏兵，就说道：“曹操此人狡猾诡诈，此地一定有埋伏，我们不能再前进了。”便引兵在南面十余里的地方安营扎寨。
第二天，吕布再次前来挑战，曹操则把自己一半的兵力都埋伏在大堤后面，另一半的士兵在大堤外面排开阵势。当吕布的军队逼近时，曹操才下令轻装部队挑战，等到两军厮杀时，曹操一声令下，埋伏在大堤后面的步兵、骑兵一齐冲出来，杀了吕布一个措手不及。吕布大败而走，曹操率兵一直追到吕布的营寨前才撤回。
吕布失败后，心情很沮丧，于是下令撤退，曹操趁机收复了兖州各部。失去地盘的吕布只得向东投靠身在徐州的刘备。张邈则留下弟弟张超驻守雍丘，自己前往袁术那里求救去了。曹操率兵包围张超，围了几个月终于攻破雍丘，杀了张超及张氏三族，张邈还没有到达寿春，就在途中被手下部卒给杀了。
