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