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