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