وكانت في مقدم قلنسوته فكان لا يلقى أحدا إلا هزمه الله تعالى وقال رسول الله صلى الله عليه وسلم اللهم هذا سيف من سيوفك فانتقم به وفي رواية نعم عبد الله وأخو العشيرة وسيف من سيوف الله سله الله على الكفار والمنافقين وكان عمر يكلم أبا بكر في عزل خالد لما حرق المرتدين وقيل يوم مالك بن نويرة وشهد قوم من السرية أنهم كانوا أذنوا وصلوا فقال عمر إن في سيفه رهقا فقال أبو بكر لا أشيم سيفا سله الله تعالى على الكفار حتى يكون الله يشيمه وقال خالد لقد قاتلت يوم مؤتة فاندق في يدي تسعة أسياف فصبرت في يدي صحيفة لي يمانية وقاتل يوم اليرموك قتالا شديدا قتل أحد عشر قتيلا منهم بطريقان وكان يرتجز ويقول * أضربهم بصارم مهند * ضرب صليب الدين هاد مهتد * وكان عمر يقول لأن صير الله هذا الأمر لأعزلن المثنى بن خارجة عن العراق وخالد بن الوليد عن الشام حتى يعلما أنما نصر الله دينه ليس إياهما نصر ولما ولي عمر قال ما صدقت الله إن كنت أشرت على أبي بكر بأمر فلم أنفذه فعزله وولى أمين الأمة أبا عبيدة بن الجراح وصار خالد أميرا من جهته فلما أجاز الأشعث بعشرة آلاف فكتب عمر إلى أبي عبيدة أن يقيم خالدا ويعقله بعمامته وينزع عنه قلنسوته ويعزله على كل حال ويقاسمه ماله ففعل ذلك وكان أبو عبيدة يكرمه ويفخمه ثم كتب عمر إلى خالد يأمره بالإقبال إليه فقدم على عمر فشكاه وقال لقد شكوتكم إلى المسلمين تالله إنك في أمري غير مجمل يا عمر واعتذر عن المال الذي فرقه بأنه من ماله فقال عمر والله إنك علي لكريم وإنك إلي لحبيب ولن تعاتبني بعد اليوم على شيء واعتذر عمر إلى الناس من أجله ثم كان عمر يذكره ويترحم عليه ويتندم على ما كان صنع به ويقول سيف من سيوف الله تعالى وقيل أن خالدا لما قدم على عمر قال متمثلا من الطويل) * صنعت فلم يصنع كصنعك صانع * وما يصنع الأقوام فالله أصنع * كتب عمر إلى الأمصار إني لم أعزل خالدا عن سخطة ولا خيانة ولكن الناس فتنوا به فخشيت أن يوكلوا إليه فأحببت أن يعلموا أن الله هو الصانع وأن لا يكونوا بعرض فتنة عن ابن الضحاك أن عمر بن الخطاب كان أشبه الناس بخالد بن الوليد فخرج عمر سحرا فلقيه شيخ فقال مرحبا بك يا أبا سليمان فنظر إليه عمر فإذا هو علقمة بن علاثة فرد عليه السلام فقال له علقمة أعزلك عمر بن الخطاب فقال له عمر نعم فقال ما يشبع لا أشبع الله بطنه فقال له عمر فما عندك قال ما عندي إلا السمع والطاعة فلما أصبح دعا بخالد وحضره علقمة بن علاثة فأقبل على خالد فقال له ماذا قال لك علقمة فقال ما قال لي شيئا فقال أصدقني فحلف خالد بالله ما لقيته ولا قال له شيئا فقال له علقمة حلا أبا سليمان فتبسم عمر فعلم