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