وقد وصف المعادلة التي دفعته إلى الدخول في الإسلام فقال : « وقلت : قد شهدت هذه المواطن كلها على محمد ، فليس موطن أشهده إلا وأنصرف وإني أرى في نفسي أني مُوضعٌ في غير شئ ، وأن محمداً سيظهر » !

وقال : « فلما جاء ( النبي ( ( ٦ ) ) ) لعمرة القضاء تغيبت ولم أشهد دخوله ، فكان أخي الوليد بن الوليد دخل معه ، فطلبني فلم يجدني ، فكتب إليّ كتاباً فإذا فيه : فإني لم أر أعجب من ذهاب رأيك عن الإسلام وقلة عقلك ، قد سألني عنك رسول الله ، فقال : أين خالد . . » . ( النهاية : ٤ / ٢٧٢ ، وتاريخ دمشق : ١٦ / ٢٢٦ ، وكثير من المصادر ) .

ومعنى : موضعٌ في غير شئ : رأيت نفسي أني أقاومه بدون نتيجة ! وكان زميله عمرو بن العاص مثله ، فقال كما رواه مجمع الزوائد ووثقه ( ٩ / ٣٥٠ ) : « لما انصرفنا من الأحزاب عن الخندق جمعت رجالاً من قريش كانوا يرون مكاني ويسمعون مني ، فقلت لهم : تعملون والله إني لأرى أمر محمد يعلو الأمور علواً منكراً ، وإني قد رأيت أمراً فما ترون فيه ؟ قالوا : وما رأيت ؟ قلت : رأيت أن نلحق بالنجاشي فنكون عنده ، فإن ظهر محمد على قومنا كنا عند النجاشي ، فإنا أن نكون تحت يديه أحب إلينا من أن نكون تحت يدي محمد ! وإن ظهر قومنا فنحن من قد عرفوا ، فلن يأتينا منهم إلا خير . قالوا : إن هذا الرأي . .

ثم وصف عمرو كيف وافقه خالد على رأيه . فقررا بعد عمرة القضاء في السنة السابعة ، أن يسلما ، وجاءا إلى المدينة وأسلما . وتاريخ الطبري : ٢ / ٣١٣ .