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