والصحيح أن إسلامه كان في صفر سنة ثمان، قدم هو وخالد بن الوليد وطلحة بن عثمان مسلمين، فلما دخلوا على رسول الله -صلى الله عليه وسلم- نظر إليهم قال:"قد رمتكم مكة بأفلاذ كبدها" وكان قدومهم على رسول الله -صلى الله عليه وسلم- مهاجرين بين الحُديبية وخيبر. قيل: إنه لم يأت من أرض النجاشيّ إلَّا معتقد الإِسلام، وذلك أنّ النجاشيّ قال له: يا عمرو كيف يَعْزُب عندك أمر ابن عمك؟ فوالله إنه لرسول الله حقًا. قال: أنت نقول ذلك؟ قال: إيْ والله، فأظعن فخرج من عنده مهاجرًا إلى النبي -صلى الله عليه وسلم-.
وذكر الزبير بن بكار أن رجلًا قال لعمرو: ما أبطاكَ عن الإِسلام وأنت أنت في عقلك؟ قال: إنّا كنا مع قوم لهم علينا تقدم، وكانوا ممن يوازي خلوبهم الخبال، فلما بعث النبي -صلى الله عليه وسلم- أنكروا عليه، فلذنا بهم، فلما ذهبوا وصار الأمر إلينا نظرنا وتدبرنا، فإذا هو حق بَيِّن، فوقع في قلبي الإِسلام، فعرفت ذلك قريش مني من إبطائي عما كنت أسرع فيه من عونهم عليه، فبعثوا إليّ رجلًا منهم، فناظرني في ذلك، فقلت: أنشدك ربك ورب من قبلك ومن بعدك، أنحن أهدى أم فارس والروم؟ قال: نحن أهدى. قلت: فنحن أوسع عيشًا أم هم؟ قال: هم، قلت: فما ينفعنا فضلنا عليهم إن لم يكن لنا فضل إلَّا في الدنيا، وهم أعظم منا فيها أمرًا في كل شيء؟ وقد وقع في نفسي أنّ الذي يقوله محمد من أن البعث بعد الموت ليُجزي المحسن بإحسانه، والمُسيء بإساءته حق، ولا خير في التمادي في الباطل.
وروي عن عمرو بن إسحاق قال: استأذن جعفر بن أبي طالب النبي -صلى الله عليه وسلم-. في التوجه إلى الحبشة، فأذن له. قال عُمير: فحدثني عمرو بن العاص قال: لما رأيت مكانه قلت: والله لأستقلنَّ لهذا وأصحابه، فذكر قصتهم مع النجاشيّ قال: فلقيت جعفر، فذهب معي خاليًا فاسلمت قال: وبلغ ذلك أصحابي فغنموني وسلبوني كل شيء، فذهبت إلى جعفر، فذهب معي إلى النجاشيّ، فردوا عليّ بكل شيء أخذوه.
ولما أسلم، كان النبي -صلى الله عليه وسلم- يقربه ويدنيه، لمعرفته وشجاعته، وأمَّره على