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