فهدد أبو سفيان خالدًا بالعقاب، فهدَّأه عكرمة قائلًا:"اهدأ يا أبا سفيان، فإن غضبك سيقودني أيضًا للانضمام إلى محمد، فخالد حر في أن يختار الدين الذي يرغبه" (10) .

وفي الليلة ذاتها أخذ خالد درعه وسلاحه وفرسه، وانطلق إلى المدينة مهاجرًا مسلمًا في صفر سنة ثمان (11) ، فقابل في الطريق عمرو بن العاص وعثمان بن طلحة اللذين توجها إلى المدينة للغاية نفسها فوصل الثلاثة إلى المدينة في الأول من صفر عام 8ه‍ /31 أيار (مايو) عام (629م) في الهدنة بعد الحديبية بين النبي ( وبين قريش، وذهبوا إلى منزل الرسول (، فأسلم خالد أولًا طوعًا، ثم تبعه عمرو، ثم عثمان.

وقيل: إنه أسلم يوم الأحزاب (وقعة الخندق) فقد جاء في الحديث: [أنه شهد خيبر، وكانت خيبر في أول سنة سبع أو سنة ست] .

فرحب بهم النبي (، وصفح عن عداوتهم السابقة، وكان ذلك نصرًا بارزًا للإسلام، لأن خالدًا وعمرو بن العاص كانا ألمع عقلين عسكريين في زمانهما.

قال خالد ذاته معبرًا عن قصة إسلامه (12) ومبينًا تأثير أخيه الوليد فيه وتأثير تشجيع النبي ( إياه على الإسلام:"لما أراد الله بي ما أراد من الخير، قذف في قلبي الإسلام وحضرني رشدي، فقلت: قد شهدت هذه المواطن كلها على محمد (، فليس في موطن أشهده إلا أنصرف، وأنا أرى في نفسي أني موضع في غير شيء، وأن محمدًا سيظهر".

فلما صالح محمد قريشًا بالحديبية، ودافعته قريش بالرواح قلت في نفسي: أي شيء بقي؟

أين أذهب إلى النجاشي! فقد اتبع محمدًا، وأصحابه آمنون، فأخرجُ إلى هرقل، فأخرج من ديني على نصرانية أو يهودية، فأقيم في عجم، فأقيم في داري بمن بقي!! فأنا في ذلك إذ دخل رسول الله ( مكة في عمرة القضية، فتغيبت ولم أشهد دخوله. وكان أخي الوليد بن الوليد، قد دخل مع النبي ( في عمرة القضية، فطلبني فلم يجدني، فكتب إلي كتابًا، فإذا فيه: