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

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

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