ثم خرجت عامدا إلى رسول الله صلى الله عليه وسلم لأسلم، فلقيت خالد بن الوليد، وذلك قبيل الفتح، وهو مقبل من مكة، فقلت: أين يا أبا سليمان؟
قال: والله لقد استقام المنسم ، وإن الرجل لنبي، أذهب والله فأسلم، فحتى متى، قال: قلت: والله ما جئت إلا لأسلم. قال: فقد منا المدينة على رسول الله صلى الله عليه وسلم، فتقدم خالد بن الوليد فأسلم وبايع، ثم دنوت، فقلت:
يا رسول الله، إني أبايعك على أن يغفر لي ما تقدم من ذنبي، ولا أذكر ما تأخر، قال: فقال رسول الله صلى الله عليه وسلم: يا عمرو، بايع، فإن الإسلام يجب ما كان قبله، وإن الهجرة تجب ما كان قبلها، قال: فبايعته، ثم انصرفت. قال ابن هشام: ويقال: فإن الإسلام يحت ما كان قبله، وإن الهجرة- تحت ما كان قبلها.