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