在董卓被杀、李等人控制朝廷后不久，刘表也派使者前往长安，向献帝表示忠心。像对待陶谦一样，长安的“三人小组”对于曾经被朝廷正式任命过的刘表也表示欢迎，刘表不仅升了一格，由刺史变为州牧，而且被同时加上了镇南将军的头衔，封为成武侯。
没有跟关东联军搅和到一块，并且与袁术刀兵相见的刘表，被李等人寄予了厚望。
刘表的使者来回都应该走武关道，这条沿着汉水南下的道路，在当年来说比今天还显得重要和热闹。刘表的使者在这条路上匆忙行走，也许会遇着一支数百人的马队，率领这支队伍的是在当时已天下闻名的飞将吕布。
吕布从长安城杀出来，虽然狼狈不堪，但所幸把他最亲近的子弟兵一块儿带了出来，综合《英雄记》等书的记载，跟随吕布杀出重围的数百人里，有他手下的得力干将张辽、高顺、成廉、魏续、魏越、侯成、宋宪等人。
这里对于吕布手下的这几个人也顺便介绍一下。张辽前面已经说过了，是资历堪与吕布相比的并州军将领，董卓死后依附于吕布。高顺是吕布手下的猛将，善长指挥骑兵作战，历来对他评价不错，因为他不仅能打，而且人品也好，不争功，不搞内斗，即使人家斗到他的头上，他也不记仇。吕布看他是难得的人才，也用他，但对他却不是很好，高顺并不在意，至死都忠心耿耿地跟着吕布。
成廉后面这几个人的详细情况都不太清楚，反正都很能打，恐怕要想让吕布看得上，这是首要条件。但他们似乎不怎么团结，看来武人也相轻。魏续、魏越或许是兄弟，他们跟吕布好像有亲戚关系，吕布对他们是无条件地信任，每当他们与高顺闹别扭，吕布总是袒护他们。
吕布领着这哥几个还有几百名骑兵顺着武关道到了南阳郡的治所宛县，见到了袁术。其后的情形有两种不同的说法。
一种说法是袁术隆重地接纳了吕布，但吕布却不好好待着，他自恃亲手杀了董卓，是袁家的恩人，所以一安顿下来就要这要那。要知道袁术此时被刘表逼迫得日子也不好过，对吕布自然不能有求必应。袁术稍有怠慢，吕布就放纵手下人去抢，结果二人的关系闹得很僵，吕布在南阳郡待不下去，就领着哥几个还有几百名骑兵走了。
另一种说法是，袁术压根没有接纳他。袁术知道吕布这个人，在丁原手下杀了丁原投董卓，在董卓手下又杀了董卓，现在来投自己，莫非自己就是下一个丁原和董卓？袁术这个人一向很迷信，也经常神经兮兮的，有这些想法也难怪。袁术不接纳，吕布无奈，只好领着人另找出路。
前一种说法来自《后汉书》，后一种说法来自《三国志》。但不管说法怎么不同，结果都差不多：吕布的南阳郡之行很失败，高兴而来，扫兴而走。
其实，即使他不走，在南阳郡也待不长，因为没有多久，袁术自己也集齐大军前往豫州、兖州方向打曹操去了。
离开袁术，吕布下一个去依靠的人是张杨。
吕布和张杨是并州老乡，过去都在丁原手下做事，董卓把持洛阳朝政以后，张杨没有像吕布和张辽那样投靠董卓，而是率领自己招募来的几千人在黄河北岸的河东郡、河内郡一带发展。这一地区也是黑山军、白波军以及南匈奴的游击区。张杨跟他们结成了一个松散同盟，在袁绍和公孙瓒之间倾向于公孙瓒。
吕布到河东郡见到了老同事张杨，但形势仍然不容乐观，长安朝廷的“三人小组”对吕布恨之入骨，一直在通缉他。张杨的防区离长安最近，早已接到悬赏捉拿吕布的通告，他手下看到长安开出的赏金很高，就想把吕布杀了换赏钱。
吕布听到风声，有点害怕，主动跟张杨说：“看在咱们是同乡的情谊上，我给你出个主意，杀了我未必划算，不如把我活着押到长安，可以得到更高的奖赏。”
吕布这话像是老朋友之间在开玩笑，那时他哪有心思开玩笑的，不过是想试探张杨的态度。但张杨却把吕布的话真当成玩笑了，所以也回了句玩笑话：“我认为你说得很对。”刘震云在《故乡、面和花朵》里开篇第一句话是：“为什么你的眼里常含满泪水，因为玩笑开得太过分。”现在吕布的眼里就该有泪水了，那是因为张杨的玩笑开得太过分。
吕布决定再跑，河东郡之行宣告失败。当然，还有一个说法，说张杨其实一直在保护吕布，在张杨的调停下，李等人也不再视吕布为仇人，他们封吕布为颖川郡太守。这个说法仅见于《英雄记》，不太靠谱，各家史书均未采纳，吕布也没有到颖川郡去上任。
偌大个中原，难道就没有我的立足之地吗？吕布思来想去，只有投袁绍了。
袁绍正与公孙瓒在冀州北部、幽州南部直至青州一线全面开战，公孙瓒虽然有界桥之战的惨败，但实力犹存，经常也压得袁绍喘不过气来。在这个时候，袁绍的左翼、也就是太行山一线又出了问题，黑山军首领张燕支持公孙瓒，袁绍派兵攻打张燕，却不见成效，袁军的一部分主力被牵制到这一线。
袁绍也不大喜欢吕布，可见做人还要讲点口碑，牌子倒了什么都没了。吕布吸取在袁术那里的教训，不敢再耍大牌，只求袁绍接纳自己，给安排个出路，干什么活都行。
袁绍看此人可利用，就派吕布带着他的人去打张燕。袁绍打张燕费劲，但吕布一出马情况就不一样，虽然人数处于劣势，但吕布连战连胜，把张燕打得很是吃不消。
并非吕布比袁绍高明多少，而是情况有了变化。张燕的主力是一支数千人的骑兵，战斗力强，机动性也强。以步兵为主的袁绍曾创造过战胜精锐骑兵的战例，但那是在双方主力的对决中，给袁绍施展谋略留下了空间，现在张燕的策略是你来我走，你走我来，比谁跑得快，这样一来袁绍就没辙了。
现在换选手了，你快，上来的人比你还快；你对地理熟悉，人家也都是从小生活在这片土地上的人，动起手来熟门熟路，一点儿都不吃亏。
吕布跟手下的成廉、魏越等人，再挑了几十个身手好的，骑上快马，组成一个突击队，专门冲击敌人的核心区，一会儿闪电战，一会儿斩首行动，来如疾风，去如迅雷，无人能挡，打得黑山军直犯迷糊。吕布是一员骁将，吕布的马也是一匹好马，打张燕不仅进一步成就了吕布的名气，也成就了吕布坐下的这匹战马。据《曹瞒传》记载，吕布在太行山下的出色表现，为他赢得了当时人所共知的两句话：马中赤兔，人中吕布。
吕布的马名叫“赤兔”，大部分史书里都这么写，但它其实还有一个叫法，叫“赤菟”，出自《后汉书》。如果仔细考察一下的话，后面这个名字似乎更恰当。
从字面上看，用“红色的兔子”来比马，实在不知道想说什么，是说马跑得快？但只能跑过兔子的马肯定还不是快马。说马的威猛？跟温顺可爱的兔子又不搭边。如果换成“赤菟”，那意思就容易理解得多。“菟”是一种植物，开一种淡红色的花，“赤菟马”就是像菟花一样颜色的马。另外，它还有一解，古人把老虎称为“於菟”，“赤菟马”就是红色的、像老虎一样威猛的马。
陈寿评价吕布用的也是类似的词，叫“虎”，意思是怒吼的猛虎。要论战斗力，吕布以及他的手下都是超一流的。但陈寿同时认为，吕布只是勇敢、勇猛，没有“英奇之略”，加上他“轻佼反覆，唯利是视”，在外界没有公信力，公众形象大打折扣，这些构成了他的致命伤。
现在，张燕被打败，退入太行山深处，袁绍侧翼的威胁解除。这时候吕布的老毛病又犯了，他自以为给袁绍立下大功，开始向袁绍伸手要这要那，要别的还好办，吕布要袁绍给自己增加部队，然后帮助自己到司隶校尉部发展。
袁绍头痛已极，让他协助吕布当上司隶校尉那是不可能的，这就好比是养一个小虎仔当宠物，不消两年功夫小虎仔长成大老虎就该吃主人了，这事吕布最拿手。袁绍经过考虑，决心除掉吕布。
这绝对是过河拆桥的做法，不管吕布既往的历史怎样，毕竟人家杀了你们家的仇人，还帮你打张燕解除你的后顾之忧，怎么说也是个功臣吧。但袁绍还是决定解决吕布。
袁绍假装答应吕布的请求，表吕布为司隶校尉，给他拨了三千甲士，随他一同去上任。《英雄记》里说袁绍派的不是三千人，而是三十人，但这不大可能，因为张辽、高顺等一直跟随吕布的嫡系应该一块儿同行，他们不会低于三百人，派区区三十个人来只能是送死。
司隶校尉的办公地点应该在洛阳，吕布一行走的路线原本是由冀州往南经河内郡渡黄河，然后往西。这是吕布计划走的线路，但不是袁绍的计划，袁绍没有打算把这趟旅行安排得那么远，他的人得到命令，半路上干掉吕布。
但吕布早有预料，他使了一计，晚上故意让袁绍的人住在自己大帐外，半夜里让人在自己的帐中弹筝，自己则悄悄逃走。袁绍人的冲进来，只能向着吕布的床乱砍一通。
袁绍得报，吓得够呛，问左右谁愿意带兵去追吕布，飞将的威名居然让袁绍手下众人无人敢应征（募遣追之，皆莫敢逼）。袁绍害怕吕布回来报复，下令关闭邺县的城门，严加防卫。
袁绍这里也没法待，吕布想找公孙瓒，但必须经过袁绍的防区，不可行。找曹操去，没有什么交情不说，听说曹操是袁绍的人，去了就得给绑上送还袁绍。吕布现在最能体会到穷途末路的含义，他想了想，还得去投老同事张杨。
吕布二次去投张杨依然没什么结果，但在此行的路上却发生了一件事，给他带来意想不到的机会，使他来了个咸鱼大翻身。