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