وهجرته سنة ثمان وقد قيل في أوّل سنة ثمان مع عمرو بن العاص وعثمان بن طلحة فلما رآهم رسول اللّه صلى اللّه عليه وسلم قال رمتكم مكة بأفلاذ كبدها قال أبو عمرو ولم يصح لخالد بن الوليد مشهد مع رسول اللّه صلى اللّه عليه وسلم قبل الفتح * وفي المواهب اللدنية كان قدومه المدينة واسلامه سنة خمس قاله ابن أبي خيثمة وقال الحاكم سنة سبع وكذا في الوفاء وفي كون اسلام خالد سنة خمس أو سبع نظر لما ورد في صحيح البخاري عن المسور بن مخرمة ومروان بن الحكم أنّ النبيّ صلى اللّه عليه وسلم قال انّ خالد بن الوليد بالغميم في خيل لقريش طليعة فخذوا ذات اليمين قاله زمن الحديبية سنة ست كذا في المشارق وهذا ينافي اسلامه سنة خمس أو سبع * وفي الصفوة خالد بن الوليد بن المغيرة بن عبد اللّه بن عمرو بن مخزوم يكنى أبا سليمان وأمّه أسماء وهي لبابة الصغرى بنت الحارث أخت أمّ الفضل امرأة عباس قال خالد لما أراد اللّه بي ما أراد من الخير قذف في قلبي حب الاسلام وحضرني رشدى وأرى في المنام كأني في بلاد ضيقة جدب فخرجت إلى بلاد أحسن وأوسع فقلت انّ هذه لرؤيا فذكرتها لأبي بكر فقال هو مخرجك الذي هداك اللّه فيه للاسلام والضيق هو الشرك فأجمعت الخروج إلى رسول اللّه صلى اللّه عليه وسلم وطلبت من أصحابه فلقيت عثمان بن طلحة فذكرت له الذي أريد فأسرع إلى الإجابة وخرجنا جميعا فأدلجنا سحرا فلما كان بالهدة إذا عمرو بن العاص فقال مرحبا بالقوم فقلنا له وبك قال أين مسيركم فأخبرناه وأخبرنا أيضا أنه يريد النبيّ صلى اللّه عليه وسلم فاصطحبنا حتى قدمنا المدينة أوّل يوم من صفر سنة ثمان فلما طلعت على رسول اللّه صلى اللّه عليه وسلم سلمت عليه بالنبوّة فردّ علىّ السلام بوجه طلق فقال صلى اللّه عليه وسلم قد كنت أرى لك عقلا رجوت أن لا يسلمك الا لخير وبايعت رسول اللّه صلى اللّه عليه وسلم فقلت استغفر لي كل ما أوضعته من صدّعن سبيل اللّه عز وجل قال انّ الاسلام يجب ما كان قبله ثم استغفر لي وتقدّم عمرو وعثمان بن طلحة فأسلما فو اللّه ما كان رسول اللّه صلى اللّه عليه وسلم من يوم أسلمت يعدل بي أحدا من أصحابه فيما يحزبه * وفي أسد الغابة فلم يزل خالد من حين أسلم يوليه رسول اللّه صلى اللّه عليه وسلم أعنة الخيل فيكون في مقدمتها في محاربة العرب وكان في مقدمة رسول اللّه صلى اللّه عليه وسلم يوم حنين في بنى سليم وجرح يومئذ فأتاه رسول اللّه صلى اللّه عليه وسلم في رحله بعد ما هزم من هوازن ليعرف خبره ويعوده فنفث في جرحه فانطلق وسيجيء وفاة خالد في الخاتمة في خلافة عمر بن الخطاب * وفي المنتقى روى أنّ عمرو بن العاص كان أسلم بالحبشة على يد النجاشي ولكن كان يكتم اسلامه من أصحابه فخرج متوجها إلى المدينة فلما كان ببعض الطريق عند الهدة إذ لقى خالد بن الوليد وهو يريد المدينة وذلك قبل الفتح فقال عمرو يا أبا سليمان أين تريد فقال خالد واللّه لقد استقام الميسم أي تبينت الطريق وظهر الامر وانّ هذا الرجل لنبىّ فاذهب فأسلم فحتى متى قال عمرو واللّه ما جئت الا لأسلم فقد ما المدينة فتقدّم خالد بن الوليد فأسلم وبايع ثم عمرو بن العاص فبايعه ثم انصرف قال ابن إسحاق وحدّثنى من لا أتهم أنّ عثمان بن طلحة بن أبي طلحة العبدري الحجبى كان معهما حين أسلما قال عثمان بن طلحة لما دخل رسول اللّه صلى اللّه عليه وسلم مكة عام عمرة القضاء غير اللّه قلبي عما كان عليه ودخلني الاسلام وجعلت أفكر فيما نحن عليه وما نعبد من حجر لا يسمع ولا يبصر ولا ينفع ولا يضرّ وأنظر إلى رسول اللّه صلى اللّه عليه وسلم وأصحابه وظلف أنفسهم عن الدنيا فيقع ذلك فأقول ما عمل القوم الاعلى الثواب ليكون بعد الموت وجعلت أحب النظر إلى رسول اللّه صلى اللّه عليه وسلم إلى أن رأيته خارجا من باب بنى شيبة يريد منزله بالأبطح فأردت أن آتيه وآخذ بيده وأسلم فلم يعزم لي ذلك فانصرف رسول اللّه صلى اللّه عليه وسلم راجعا إلى المدينة ثم عزم لي على الخروج إليه فأدلجت إلى بطن يأجج فألقى خالد بن الوليد فاصطحبنا حتى نزلنا الهدة فما شعرنا