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