吕布在李傕等人攻占长安之时，与李傕交锋失败，带了几百名亲信骑兵，离开长安，逃出武关，到南阳投奔袁术。
为了便于和袁术见面，他于百忙之中，知道割下董卓尸首的头，拴在马颈项上。董卓曾经杀过袁绍与袁术留在洛阳的家属，所以吕布拿董卓的头，送给袁术作见面礼。
果然袁术对他很好，准他在南阳安顿下来。他得意之余，忘记了约束自己几百名的部下，随他们任意骚扰百姓，甚至奸淫掳掠也干。这就激怒了袁术，吕布看见颜色不对，便匆匆告辞，向北走，由南阳到洛阳，由洛阳过黄河，投奔那据有河内（怀庆）的张扬。
张扬也是并州人，算来为吕布的同乡，而且曾经同为丁原的部下，又可谓老同事（在丁原被吕布倒戈之时，张扬本人不在洛阳，而在山西东南部的上党郡，奉何进之命扫荡草寇，尚未完成任务。丁原既死，他在上党就竖起反旗，自己做起草寇来，攻打上党太守于山西壶关，壶关他打不下来，就移兵到豫北。占领当时的河内郡，董卓顺水推舟，发表他为河内太守）。
他和吕布二人，本来私交颇好，现在，吕布既不远千里而来，走来投奔他，他也就表示欢迎。
不过张扬部下的高级军官，多数看不起吕布，甚至不肯忘记吕布杀过丁原，因为他们也是并州人，跟随过丁原的。尽管张扬待吕布好，他们仍旧想杀了吕布，到长安李傕、郭汜那里，一方面可以请赏，另一方面还可以替死了的丁原来出气。
吕布聪明得很，看出形势不对，他就向张扬说：“听说长安政府通缉我，赏格很高，你和我是同乡，与其杀了我去领赏，倒不如活捉我押解去，可以领得多点。”
张扬实在不曾有杀他的意思，听了吕布的话不免生气，就顺着吕布的口气，也不解释这只是部下存有此心，而他本人毫无此意，他对吕布说：“你的看法很对，与其杀了你去请赏，倒不如把你捉了，送个活的到长安，赏金可以多些。”
这一来，却把吕布吓坏了，索性不辞而别，溜到邺县（河南临漳），去投袁绍。
袁绍知道吕布能干，把他留了下来，并且叫他帮忙讨伐常山（河北正定）的黑山贼张燕。这张燕绰号张飞燕，骑马如飞，原本姓褚，是博陵大盗张牛角的好朋友，于张牛角死的时候，继统他的部下，改姓了张。他逐渐扩充，居然跨有河北、山西、河南三省交界之处，有一百多万人之多，号称为黑山贼，与黄巾互相呼应。汉灵帝的朝廷有本领解决张角、张梁、张宝，却不能奈何张燕。
当袁绍袭夺了韩馥的冀州，又与幽州的公孙瓒交锋之时，张燕与公孙瓒结成一气，所以袁术在打平公孙瓒以后，就去打他，却好有吕布跑来帮忙。
吕布骑在赤兔马上，可以飞上城墙，跳过深沟，张燕尽管绰号飞燕，却要逊他一筹。吕布带了几十个老部下（原来有几百个，只剩下几十个了），天天冲进张燕的阵营，把张燕的人杀得落花流水，这样一连搅了十几天，张燕的实力大受影响，只好让出正定一带的地盘，躲到山里头去。
那时候，一般兵士与人民都佩服吕布的英勇，流行了两句谚语：“马中有赤兔，人中有吕布。”
吕布表现得太好，引起了袁绍的猜忌，吕布请求增加兵员，袁绍不准，吕布和他的部下，发起老脾气来，奸淫掳掠一顿，袁绍大不开心。
吕布感觉到此地又非藏身之处，便表示要回洛阳。袁绍就以盟主的资格，代表皇帝命令吕布为“署理”司隶校尉。司隶校尉之官，用清朝的制度来比仿，便是“直隶总督”，而当时的直隶，不是河北省，而是宝鸡至郑州的一个地方，包括长安洛阳在内。自然，吕布获得了“司隶校尉”之名，不仅无法治理潼关以西仍为李傕、郭汜所占据的地域，也没有多大力量可以治理洛阳一城。洛阳自从被董卓烧了以后，荒凉得很，是群盗出没的所在。
是袁绍太不光明，发表了吕布为司隶校尉，却又派人假装替他饯行，暗图谋害。吕布机警得很，临时自动要求表演弹琴（筝），他在帐篷里弹了一会，便换人代弹，帐篷外边的袁绍刺客，还以为他正在越弹越高兴，其实他已经骑了赤兔马，独自一人溜走了。