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