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