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

أنبأنا أبو جعفر بن أحمد بن علي بإسناده إلى يونس بن بكير، عن ابن إسحاق قال:

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

واستعمله رسول الله صلى الله عليه وسلم على عمان، فلم يزل عليها إلى أن توفي رسول الله صلى الله عليه وسلم.