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