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