吕布字奉先,是五原郡九原县人。他凭借勇猛的武艺在并州任职。刺史丁原担任骑都尉,驻扎在河内,任命吕布为主簿,对他十分亲近信任。汉灵帝去世后,丁原率领军队前往洛阳,和何进谋划诛杀宦官,被任命为执金吾。何进失败后,董卓进入京城,想要作乱,打算杀掉丁原,吞并他的军队。董卓因为吕布被丁原信任,就引诱吕布让他杀掉丁原。吕布斩杀丁原的首级去拜见董卓,董卓任命吕布为骑都尉,非常宠爱信任他,还发誓结为父子。
吕布擅长骑马射箭,体力过人,号称 “飞将”。他逐渐升任中郎将,被封为都亭侯。董卓知道自己待人无礼,担心有人谋害自己,出行起居常常让吕布护卫。但董卓性情刚愎狭隘,一发脾气就不顾后果,曾经因为一点小事不如意,就拔出手戟掷向吕布。吕布身手敏捷躲开了,随后向董卓道歉谢罪,董卓的怒气才消解。从此吕布心里暗中怨恨董卓。董卓经常让吕布守卫内阁,吕布和董卓的侍女私通,担心事情败露,心里很不安。
在此之前,司徒王允因为吕布是同乡又勇猛健壮,就用心接纳他。后来吕布去拜见王允,诉说自己差点被董卓杀掉的事情。当时王允和仆射士孙瑞秘密谋划诛杀董卓,就把这件事告诉吕布,让他做内应。吕布说:“那我们名义上是父子,该怎么办呢?” 王允说:“你本来姓吕,和他没有骨肉关系。现在你担心被杀都来不及,还谈什么父子?” 吕布于是答应了,亲手刺杀了董卓。这件事的详细情况记载在《董卓传》里。王允任命吕布为奋武将军,授予符节,礼仪待遇等同于三司,又进封他为温侯,和他一起执掌朝政。吕布自从杀掉董卓后,就畏惧厌恶凉州人,凉州人也都怨恨他。因此李傕等人就联合起来回军攻打长安城,吕布抵挡不住,李傕等人于是进入了长安。董卓死后六十天,吕布也战败了,他率领几百名骑兵逃出武关,想要去投奔袁术。
吕布认为自己杀掉董卓是为袁术报了仇,想以此让袁术感激自己。但袁术厌恶他反复无常,拒绝接纳他。吕布于是向北投奔袁绍,袁绍和吕布一起在常山攻打张燕。张燕有一万多精兵,几千名骑兵。吕布有一匹好马名叫赤兔,他常常和亲近的将领成廉、魏越等人冲锋陷阵,最终打败了张燕的军队。之后吕布请求增加兵力,而他的将士们却到处抢掠,袁绍对此感到担忧和猜忌。吕布察觉到