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

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

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