أول مشاهد خالد مع النبي صلى الله عليه وسلم فتح مكة، قال ابن عبدالبر: لا يصح لخالد بن الوليد مشهد مع رَسُول اللَّهِ صَلَّى اللَّهُ عَلَيْهِ وَسَلَّمَ قبل الفتح ..

وفي الفتح كان على خيل لرسول الله صل الله عليه وسلم، وأمره أن يدخل من أعلى مكة من كداء، ودخل النبي صلى الله عليه وسلم من كُدا، فقُتل من خيل خالد بن الوليد رضي الله عنه يومئذ رجلان: حبيش بن الأشعر، وكرز بن جابر الفهري رضي الله عنهم أجمعين.

كان خالد على مجنبة النبي اليمنى، والزبير على مجنبته اليسرى، وأبو عبيدة على البياذقة وبطن الوادي.

ولما ظهر رسول اللَّه صلّى اللَّه عليه وسلّم على ثنيّة أذاخر نظر إلى البارقة فقال: «ما هذا؟ ألم أنه عن القتال» ، فقيل: يا رسول اللَّه، خالد بن الوليد قوتل فقاتل. فقال: «قضاء اللَّه خير»

قال: وجعل خالد بن الوليد يتمثل وهو يقاتل بقول خارج بن خويلد الخزاعي الكعبيّ:

إذا ما رسول اللَّه فينا رأيتنا ... كلجّة بحر مال فيها سريرها

إذا ما ارتديناها فإنّ محمّدا ... لها ناصر عزّت وعزّ نصيرها

وجَذيمة، هو ابن عامر بن عبد مناه بن كنانة، بعث إليهم النبي صلى الله عليه وسلم خالدا، وهذا البعث كان عقب فتح مكة في شوال قبل الخروج إلى حنين، وكانوا بأسفل مكة من ناحية يلملم.

قال ابن عبدالبر: وبعثه رَسُول اللَّهِ صَلَّى اللَّهُ عَلَيْهِ وَسَلَّمَ أيضا إلى الغميصاء ماء من مياه جَذيمة من بني عامر، فقتل منهم ناسا لم يكن قتله لهم صوابا، فوداهم رَسُول الله صلى الله عليه وسلم، وقال: اللَّهمّ إني أبرأ إليك مما صنع خالد بن الوليد، وخبره بذلك من صحيح الأثر، ولهم حديث ..

يريد حديث ابن عمر، قال: بعث النبي صلى الله عليه وسلم خالد بن الوليد إلى بني جذيمة، فدعاهم إلى الإسلام، فلم يحسنوا أن يقولوا: أسلمنا، فجعلوا يقولون: صبأنا، صبأنا، وجعل خالد بهم أسرا وقتلا، قال: ودفع إلى كل رجل منا أسيرا، حتى إذا أصبح يوما، أمر خالد أن يقتل كل رجل منا أسيره، قال ابن عمر: فقلت: والله لا أقتل أسيري، ولا يقتل رجل من أصحابي أسيره، قال: فقدموا على النبي صلى الله عليه وسلم فذكروا له صنيع خالد، فقال النبي صلى الله عليه وسلم ورفع يديه:"اللهم إني أبرأ إليك مما صنع خالد"مرتين ..

وهذه الحادثة جرَّت عليه كلام بعضَ مَن كان معه مِنْ فقهاء الصحابة.