قال: فقدمنا على رسول الله، ﷺ، المدينة، فتقدّم خالد بن الوليد فأسلم وبايع، ثم دنوت فقلت: يا رسول الله، إنى أبايعك أن يغفر لى ما تقدّم من ذنبى ولا أذكر ما تأخر.. فقال رسول الله ﷺ: «يا عمرو، بايع، فإن الإسلام يجبّ ما قبله «١» - وفى رواية محمد بن إسحاق: يهدم ما كان قبله- وإنّ الهجرة تجبّ ما كان قبلها» . قال: فبايعته ثم انصرفت.
وروى عن عمرو بن العاص، رضى الله عنه، أنه قال: بعث إلىّ رسول الله ﷺ فقال: «خذ عليك ثيابك وسلاحك» .. قال: فأخذت علىّ ثيابى وسلاحى، ثم أقبلت إلى رسول الله، ﷺ، فوجدته يتوضّأ، فصوّب النظر ثم طأطأه، ثم قال: «يا عمرو، إنى أريد أن أبعثك على جيش يغنمك الله ويسلمك «٢» ، وأرغب إليك رغبة من المال صالحة» . فقلت: والله يا رسول الله ما أسلمت للمال، ولكن أسلمت رغبة فى الإسلام، وأن أكون معك..
فقال: «يا عمرو «٣» ، نعم المال الصّالح مع الرجل الصالح» «٤» .
فوجّهه رسول الله ﷺ إلى السلاسل «٥» من بلاد قضاعة فى ثلاثمائة، فكتب إلى رسول الله ﷺ يستمدّه، فأمدّه بجيش فيه مائتا فارس من المهاجرين والأنصار من أهل الشرف، منهم أبو بكر وعمر، رضى الله عنهم.