سیدنا عمرو بن عاص رضی اللہ عنہ سے روایت ہے، انہوں نے براہِ راست بیان کیا: میں (اسلام قبول کرنے کے) ارادے سے رسول اللہ صلی اللہ علیہ وسلم کی طرف نکلا تو راستے میں خالد بن ولید سے ملاقات ہوئی، یہ فتحِ مکہ سے کچھ عرصہ پہلے کی بات ہے اور وہ مکہ سے آ رہے تھے، میں نے پوچھا: اے ابو سلیمان! کہاں کا ارادہ ہے؟ انہوں نے کہا: اللہ کی قسم! راستہ واضح ہو چکا ہے، یقیناً وہ شخص (محمد صلی اللہ علیہ وسلم ) اللہ کے نبی ہیں، میں جا کر اسلام قبول کر رہا ہوں، آخر کب تک (حق سے دور رہوں گا)؟ وہ بیان کرتے ہیں کہ پھر ہم رسول اللہ صلی اللہ علیہ وسلم کی بارگاہ میں مدینہ حاضر ہوئے، خالد بن ولید نے آگے بڑھ کر اسلام قبول کیا اور بیعت کی، پھر میں نے قریب ہو کر بیعت کی اور واپس لوٹ آیا۔ [المستدرك على الصحيحين/كِتَابُ مَعْرِفَةِ الصَّحَابَةِ رَضِيَ اللهُ تَعَالَى عَنْهُمْ/حدیث: 5377]

وحشی بن حرب اپنے دادا سے روایت کرتے ہیں کہ سیدنا ابوبکر صدیق رضی اللہ عنہ نے خالد بن ولید رضی اللہ عنہ کو مرتدین کے خلاف قتال کے لیے روانہ کیا، تو اس بارے میں ان سے گفتگو کی گئی، مگر انہوں نے خالد رضی اللہ عنہ کو واپس بلانے سے انکار کر دیا اور فرمایا: میں نے رسول اللہ صلی اللہ علیہ وسلم کو خالد بن ولید کا تذکرہ کرتے ہوئے سنا ہے، آپ صلی اللہ علیہ وسلم نے فرمایا تھا: ”وہ اللہ کا بہترین بندہ، قبیلے کا بہترین بھائی اور اللہ کی تلواروں میں سے ایک تلوار ہے۔“ [المستدرك على الصحيحين/كِتَابُ مَعْرِفَةِ الصَّحَابَةِ رَضِيَ اللهُ تَعَالَى عَنْهُمْ/حدیث: 5378]