效力董卓
吕布因其勇武在并州任职,并州刺史丁原担任骑都尉,在河内驻扎,任命吕布为主簿,对他很亲近。汉灵帝死后,丁原接到何进的徵召,率领军队到洛阳,密谋诛杀宦官,被任命为执金吾。适逢何进为宦官所杀,董卓入京,诱吕布杀丁原,进而吞并丁原的军队,并任命吕布为骑都尉,同他发誓结为父子,对他十分欣赏信任。吕布善长骑射,膂力过人,被称为“飞将”,不久又被董卓提拔为中郎将,封都亭侯。
关东军起兵讨董时,吕布亦曾参战,却与将领胡轸不和而被孙坚所败,最后董卓挟天子迁都长安。董卓自知自己凶暴,为人所恶,所以时常要吕布作自己的侍卫及守中阁;不过,董卓性格又十分猜疑,曾因小许失意而向吕布掷出手戟,又吕布与董卓的婢女有染,恐怕事情被董卓发觉,所以心中十分不安。之前,由于王允因为吕布是并州的壮士,对他以厚礼相待。自从吕布怀恨董卓后,他去见了王允,述说了董卓差点杀他的经过。王允此时正和士孙瑞、杨瓒等密谋除掉董卓,因此便让吕布作内应。吕布有些犹豫,说:“奈何是父子,怎么好下手呢?”王允说:“将军姓吕,本来就非亲生骨肉,如今你保全自己的性命还来不及,还说什么父子!”于是吕布答应了王允,成功刺杀董卓,任职奋武将军,假节,仪比三司,进封温侯,与王允同掌朝政。
投靠各方
董卓死后两个月,其旧部属李傕和郭汜等本想解散部队,归隐田野,途中遇贾诩献计,召集旧部,攻入京城,吕布守城八日,因城内叟兵叛变,吕布战败,于是率兵百余骑兵,带着董卓的首级杀出武关。在此期间,吕布曾在城北与郭汜单挑决胜负,吕布以矛刺中郭汜,郭汜被左右军队所救,双方遂各自罢兵。
吕布先投靠袁术,但因袁术不满他自恃有功而十分骄恣、恣兵抄掠,所以被拒绝,于是吕布改投袁绍。在袁绍处,与其联手在常山会战张燕,黑山军有一万多精兵、几千骑兵。吕布经常骑着能够腾跃城墙、飞跨壕沟、名叫赤兔的良马,与手下猛将成廉、魏越等几十个人骑马冲击张燕的军阵,有时一天去三四次,每次都砍了黑山军的首级回来。连续作战十多天,终于打败了张燕的军队。吕布仗恃自己的战功,再次向袁绍要求增加军队,袁绍不答应,而吕布手下的将士也时时抢劫、掠夺,袁绍开始疑恨他。吕布感觉不安,就请求回洛阳。袁绍同意他的要求,以天子名义任命吕布领司隶校尉,派甲士送吕布而暗中要除掉他。吕布怀疑袁绍打自己的主意,就派人在营帐中弹着筝,自