خالد رضي الله عنه زوجة مالك بن نويرة وكانت من أجمل النساء. ويقال إن خالدا استدعى مالك بن نويرة وقال له: كيف ترتد عن الإسلام وتمنع الزكاة؟ ألم تعلم أن الزكاة قرينة الصلاة؟ فقال: كان صاحبكم يزعم ذلك، فقال له: هو صاحبنا وليس هو بصاحبك، يا ضرار اضرب عنقه، وأمر برأسه فجعل ثالث حجرين جعل عليها قدر يطبخ فيه لحم، فعل ذلك إرجافا لأهل الردة، فلما بلغ سيدنا عمر ذلك قال للصديق رضي الله تعالى عنهما اعزله، فإن في سيفه رهقا كيف يقتل مالكا ويأخذ زوجته؟ فقال الصديق رضي الله تعالى عنه: لا أغمد سيفا سله على الكافرين والمنافقين، سمعت رسول الله صلى الله عليه وسلم يقول:«نعم عبد الله وأخو العشيرة خالد بن الوليد سيف من سيوف الله سله الله على الكافرين والمنافقين» وقال الصديق رضي الله تعالى عنه في حق خالد: عجزت النساء أن يلدن مثل خالد بن الوليد.
وفي كلام السهيلي أنه روي عن عمر بن الخطاب أنه قال لأبي بكر الصديق:
إن في سيف خالد رهقا فاقتله، وذلك حين قتل مالك بن نويرة وجعل رأسه تحت قدر حتى طبخ به، وكان مالك ارتد ثم رجع إلى الإسلام ولم يظهر ذلك لخالد، وشهد عنده رجلان من الصحابة برجوعه إلى الإسلام فلم يقبلهما وتزوج امرأته، فلذلك قال عمر لأبي بكر اقتله، فقال: لا أفعل لأنه متأول، فقال: اعزله، فقال: لا أغمد سيفا سله الله تعالى على المشركين، ولا أعزل واليا ولاه رسول الله صلى الله عليه وسلم.
قيل وأصل العداوة بين خالد وسيدنا عمر رضي الله تعالى عنهما على ما حكاه الشعبي أنهما وهما غلامان تصارعا، وكان خالد ابن خال عمر، فكسر خالد ساق عمر فعولجت وجبرت.
ولما ولي سيدنا عمر رضي الله تعالى عنه الخلافة أوّل شيء بدأ به عزل خالدا لما تقدم، وقال: لا يلي لي عملا أبدا. وقيل لكلام بلغه عنه، ومن ثم أرسل إلى أبي عبيدة: إن أكذب خالد نفسه فهو أمير على ما كان عليه، وإن لم يكذب نفسه فهو معزول، فانتزع عمامته وقاسمه ماله نصفين فلم يكذب نفسه، فقاسمه أبو عبيدة ماله حتى إحدى نعليه وترك له الأخرى وخالد يقول: سمعا وطاعة لأمير المؤمنين.
وبلغه أن خالدا أعطى الأشعث بن قيس عشرة آلاف وقد قصده ابتغاء إحسانه، فأرسل لأبي عبيدة أن يصعد المنبر ويوقف خالدا بين يديه وينزع عمامته وقلنسوته ويقيده بعمامته، لأن العشرة آلاف إن كان دفعها من ماله فهو سرف، وإن كان من مال المسلمين فهي خيانة، فلما قدم خالد رضي الله تعالى عنه على عمر رضي الله تعالى عنه قال له: من أين هذا اليسار الذي تجيز منه بعشرة آلاف؟ فقال: من الأنفال والسهمان، قال: ما زاد على التسعين ألفا فهو لك، ثم قوّم أمواله وعروضه وأخذ منه عشرين ألفا، ثم قال له: والله إنك عليّ لكريم، وإنك لحبيب، ولم تعمل لي