اما داستان مسلمان شدن او:
هنگامی که خداوند اسلام را در دل عمرو بن عاص سانداخت، برای ملاقات با رسول الله و دخول در اسلام از مکه خارج شد.
عمرو سمیگوید: با خالد بن ولید مواجه شدم و آن زمان اندکی قبل از فتح مکه بود و او از مکه میآمد، گفتم: کجا میروی اى ابوسلیمان؟ گفت: بخدا قسم راه را یافتهام. آن مرد(محمد ص) پیامبر است و من میروم تا اسلام بیاورم، تا چه وقت(حقیقت را نپذیرم)؟ گفتم: قسم بخدا من نیز تنها برای اسلام آوردن آمدهام، پس وارد مدینه شدیم و نزد رسول الله صرفتیم و خالد جلو رفت و اسلام آورد و بیعت کرد و من نیز نزدیک شدم، و گفت: ای رسول خدا من در صورتی بیعت میکنم که گناهان قبل من بخشوده شود، اما گناهان مابعد را نمیدانم. رسول الله صفرمود: ای عمرو بیعت کن، چرا که اسلام تمام گناهان قبل را میبخشد و هجرت نیز گناهان قبل از خود را قطع میکند.
گفت: بیعت کردم و سپس رفتم[٧٩].
وقتی که خالد همراه عمرو بن عاص مسلمان شد، پیامبر صگفت: مکه جگر گوشههایش را به سوی شما میاندازد، و پیامبر صفرمود: خداوندا خالد را بخاطر آنچه که در مخالفت تو و راه حق انجام داده است، بیامرز.
خالد گفت: قسم بخدا روزی که مسلمان شدم، رسول الله صدر مسائل مربوط به جنگ، هیچکدام از صحابه را همردیف من قرار نمیداد. (برایم جایگاه ویژهای در نظر میگرفت).
[٧٩] احمد ، مسند، ۴/۱٩۸-۱٩٩؛ بیهقی، السنن الکبری، ٩/۱۲۳، حاکم، المستدرک۳/۴۵۴ و آلبانی در الارواء سند آن را حسن دانسته است ۵/۱۲۲-۱۲۳.