قال: فما الذي أخرجكم؟ قلنا: الدخول في الإسلام وإتباع محمد. قال: وذاك الذي أقدمني.

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

قال خالد - رضي الله عنه -: وتقدم عمرو وعثمان فبايعا رسول الله - صلى الله عليه وسلم -، وكان قدومنا في صفر من سنة ثمان، فو الله ما كان رسول الله - صلى الله عليه وسلم - من يوم أسلمتُ يعدل بي أحداً من أصحابه فيما حَزبهُ.

قلت: وذكره أيضاً ابن عساكر في تاريخه.