وكان أخى الوليد بن الوليد قد دخل مع النبى صلى الله تعالى عليه وسلم فى عمرة القضاء فطلبنى، فلم يجدنى، فكتب إلى كتابا فإذا فيه:
بسم الله الرحمن الرحيم، أما بعد فإنى لم أر أعجب من ذهاب رأيك عن الإسلام، وعقلك عقلك، ومثل الإسلام ما جهله أحد، وقد سألنى رسول الله صلى الله تعالى عليه وسلم عنك، وقال:
أين خالد، فقلت: يأتى الله تعالى به، فقال: ما مثله يجهل الإسلام؟!، ولو كان جعل نكايته وحده مع المسلمين كان خيرا له، ولقدمناه على غيره، فاستدرك يا أخى ما قد فاتك من مواطن صالحة» .
فلما جاءنى كتابه نشطت للخروج، وزادنى رغبة فى الإسلام، سؤال رسول الله صلى الله تعالى عليه وسلم عنى، وأرانى فى المنام كأنى فى بلاد ضيقة مجدبة، فخرجت فى بلاد خضراء واسعة، فقلت إن هذه لرؤيا، فلما أن قدمت المدينة المنورة قلت لأذكرنها لأبى بكر، فقال: مخرجك الذى هداك الله تعالى للإسلام، والضيق الذى كنت فيه من الشرك.
فلما أجمعت الخروج إلى رسول الله صلى الله تعالى عليه وسلم قلت: من أصاحب إلى الرسول صلى الله تعالى عليه وسلم!!، فلقيت صفوان بن أمية، فقلت: يا أبا وهب، أما ترى ما نحن فيه، إنما نحن كأضراس، وقد ظهر محمد صلى الله تعالى عليه وسلم على العرب والعجم، فلو قدمنا على محمد واتبعناه، فإن شرف محمد شرف لنا، فأبى أشد الإباء، وقال لو لم يبق غيرى ما اتبعته أبدا، فافترقنا وقلت هذا رجل قتل أخوه وأبوه ببدر، قلت فاكتم على فلقيت عكرمة بن أبى جهل، فقال مثل ما قال صفوان بن أمية فخرجت إلى منزلى فأمرت براحلتى، فخرجت بها إلى أن لقيت عثمان بن أبى طلحة، فقلت إن هذا لى صديق فلو ذكرت له ما أرجوه، ثم ذكرت من قتل من آبائه فكرهت أن أذكره، فقلت وما على، وأنا راحل من ساعتي، فذكرت له ما آل الأمر إليه، فقلت إنما نحن بمنزلة ثعلب فى جحر لو صب عليه ذنوب من ماء لخرج، وقلت له نحوا مما قلت لصاحبى، فأسرع الإجابة وقلت له إنى غدوت إليهم، وأنى أريد أن أغدو، وهذه راحلتى ... فأدلجنا سرا، فلم يطلع علينا الفجر، حتى التقينا فغدونا حتى انتهينا إلى الهدة. فوجدنا عمرو بن العاص، بها، فقال: مرحبا بالقوم، فقلنا: وبك، فقال إلى PageV03P839 # أين مسيركم؟ فقلنا وما أخرجك؟ فقال وما أخرجكم؟ قلنا الدخول فى الإسلام، واتباع محمد صلى الله تعالى عليه وسلم، قال وذلك الذى أقدمنى، فاصطحبنا جميعا حتى دخلنا المدينة المنورة، فأنخنا بظهر الحرة ركابنا فأخبر بنا رسول الله صلى الله تعالى عليه وسلم فسربنا فلبست من صالح ثيابى، ثم عمدت إلى رسول الله صلى الله تعالى عليه وسلم، فلقينى أخى فقال: أسرع فإن رسول الله صلى الله تعالى عليه وسلم قد أخبر بك فسر لقدومك، وهو ينتظركم، فأسرعنا المشى، فاطلعت عليه، فما زال يبتسم لى حتى وقفت عليه، فسلمت عليه بالنبوة، فرد على السلام بوجه طلق، فقلت إنى أشهد أن لا اله إلا الله، وأنك رسول الله صلى الله تعالى عليك وسلم، فقال تعال، ثم قال رسول الله صلى الله تعالى عليه وسلم: «الحمد لله الذى هداك، قد كنت أرى لك عقلا، ورجوت ألا يسلمك إلا إلى خير» قلت يا رسول الله، إنى قد رأيت ما كنت أشهد من تلك المواطن عليك مما أبرأ منه فادع الله أن يغفر لى ذلك، فقال رسول الله صلى الله تعالى عليه وسلم: «الإسلام يجب ما كان قبله» ، قلت يا رسول الله على ذلك فقال صلى الله تعالى عليه وسلم «اللهم اغفر لخالد بن الوليد، كل ما أوضع فيه من صد عن الله ورسوله» .