吕布的「三国第一武将」，正式成型于《三国演义》，曾经的说书人更是把「一吕二马三典韦四关五马六张飞七许八夏九姜维」的排名传播得家喻户晓。
至于这个名声是怎么来的，我们首先得说清楚：史书里的吕布是怎样的?
吕布的初始形象与《三国演义》的描述确有一定相似性，尤其《三国志》作者陈寿更是评价他「有虓虎之勇，而无英奇之略，轻狡反复，唯利是视」，并将此视为他败亡的原因。
然而，史书里的种种记载，却未必都符合这一评价，描画的吕布也不像《三国演义》那么简单化。
在武力方面，吕布堪称骁勇，《三国志》说他「以骁武给并州」「便弓马，膂力过人，号为飞将」，更令人称奇的是「辕门射戟」实有其事，吕布凭此消除了袁术大将纪灵与刘备间的战端。
然而，吕布也并非无敌，除了「辕门射戟」这一典故，其他那些关于他武勇的描述基本属于边地武将标配，董卓也「膂力少比，双带两鞬，左右驰射」，吕布同乡张杨也「以武勇给并州」。更重要的是他还有数次被击败的记录，孙坚就两次打败他，其中第二次更是孙坚军进了洛阳城门，与吕布短兵相接，使之破走;《三国志·武帝纪》里还记载了他被一名不见经传的「县人李进」所破的事迹。
另外，尽管陈寿评价吕布无略，《后汉书》里陈登也说他「勇而无谋」，但吕布有谋略的事迹却也不少。如他看穿袁绍派人暗杀他的意图，使人「鼓筝于帐中」，自己金蝉脱壳。在《三国志·王允传》里，知道杀死董卓后应取其聚敛安抚部众的也是他。而之所以会有「辕门射戟」，也是吕布本人意识到刘备被袁术消灭后的局势将不利于己。
而且，吕布在丁原帐下任主簿，属于笔杆子角色，这一特长也被他用在了后来的政治生涯中。东海萧建为琅邪相，治莒，保城自守，吕布写信给他道：
天下举兵，本以诛董卓耳。布杀卓，来诣关东，欲求兵西迎大驾，光复洛京，诸将自还相攻，莫肯念国。布，五原人也，去徐州五千余里，乃在天西北角，今不来共争天东南之地。莒与下邳相去不远，宜当共通。君如自遂以为郡郡作帝，县县自王也!昔乐毅攻齐，呼吸下齐七十余城，唯莒、即墨二城不下，所以然者，中有田单故也。布虽非乐毅，君亦非田单，可取布书与智者详共议之。
先说明自己纯为匡扶汉室，作为西北人也并不想在东南割据，再提出莒与下邳相去不远，宜当共通，最后以「君亦非(守住莒城的)田单」暗示武力威胁。把外交辞令运用得非常巧妙，也取得了应有的效果：信件一出，萧建即送礼交好。
最后，关于吕布的最终败亡，《三国演义》与正史记载有重大出入：吕布并非为叛变部将所擒，而是主动投降，且据《后汉书》记载，有为保全下属，令左右取其首级献给曹操的举动，左右不忍心，才直接向曹军投降。
总的来说，史书里的吕布有符合「有勇无谋、见利忘义」的一面，也有闪现智谋与人格的一面。但出处有一定规律，表现武勇和见利忘义的材料，《三国志》与《后汉书》中都可见到;而突出其人格的描述，就主要是在《后汉书》里，《三国志》中几乎没有;那些表现吕布智谋的事迹，则是裴松之引《英雄记》才让今人得见。
这种史料互相矛盾，同见于正史的情况并不罕见。吕布两番「转会」，都手刃前任主公，尽管为他所杀之丁原、董卓都是虎狼之辈，也还是犯了当时最大的政治正确。陈寿在对他的评价后面加一句「自古及今，未有若此不夷灭也」，有明显的道德劝喻意味，对中国古代史家而言，为这样的目的选取材料本身也是正当的。
此后文人围绕吕布的评价与创作，很少脱离过陈寿搭好的框架。宋元话本流行，诸如吕布为赤兔马杀丁原、为貂蝉杀董卓以及虎牢关「三英战吕布」等虚构故事也都被创作出来，人格一再被贬低的同时，武力也不断增强，他的武器也被换成唐代以后才有使用且难度极大的画戟。
不过，吕布正式登上「第一武将」宝座还是在《三国演义》成书之时，原因倒也十分简单：《三国演义》的写作年代，「三英战吕布」这样的故事已被话本传播得家喻户晓，绝不可弃;然而它的主要褒扬对象却是刘关张，其中关羽更是武艺与忠义的结合体。
要想兼顾这两点，那就有必要把吕布的武艺拔高到出神入化，正如毛宗岗所论：「写吕布声势、愈衬刘、关、张声势。」为此，《三国演义》特别原创了曹军许褚、典韦、夏侯惇、夏侯渊、李典、乐进六员名将合力才将吕布击退的桥段，纪灵更是被他「一把扯回，如提童稚」，如此，才可以保留「三英战吕布」，又不至于贬低了刘关张三人的武艺。