وهما جَيْفر وعباد ابنى الجلندى [وكان ذلك فى العام التاسع الهجرى] فدخلا الإسلام، ولكنه [أى عمرو] لم يتمكن من رؤية الرسول [-صلى اللَّه عليه وسلم-] مرة أخرى حيث وصله نبأ وفاته وهو فى عمان وكان ذلك سببا لعودته للمدينة، ولكنه لم يبق بها لفترة طويلة.
وفى عام ١٢ هـ/ ٦٣٣ م أرسله أبو بكر [رضى اللَّه عنه] على رأس جيش إلى فلسطين وإن كانت أنباء ذلك الفتح تبدو إلى حد ما مضطربة ولكن من المؤكد أن عمرو بن العاص قد لعب دورًا بارزًا فى تلك المهمة.
ويعتبر إخضاع هذا القطر الواقع غرب الأردن من إنجازاته، كما أنه كان موجودًا أيضًا فى معركتى أجنادين واليرموك وكذلك عند فتح دمشق.
وترجع شهرة عمرو الحقيقية إلى قيامه بفتح مصر، وعلى ضوء ما ورد فى بعض المصادر يتضح أنه قاد قواته على مسئوليته الشخصية ومع ذلك فمن الأرجح أن عمر بن الخطاب رضى اللَّه عنه قد تم إخطاره بذلك الأمر أو أن ذلك الأمر قد تم بناء على أوامره.
ومن المؤكد أنه أرسلت إليه [أى لعمرو] فى الحال الإمدادات بقيادة الزبير، على أن ما يجب الاكتفاء بذكره هنا هو أنه فى صيف عام ١٩ هـ/ ٦٤٠ م تمت هزيمة الروم فى هليوبوليس [عين شمس] كما استولى العرب فى السنة التالية ٢٠ هـ/ ٦٤١ م على حصن بابليون ثم كان وقوع الإسكندرية فى قبضتهم عام ٢١ هـ/ ٦٤٢ م.
هذا ولم يكن فتح مصر هو أحد أعمال العبقرى عمرو بن العاص فقط ولكنه أيضا عين واليا عليها وقام بتنظيم إدارتها وقضائها والضرائب. كما أسس مدينة الفسطاط التى عرفت فيما بعد بمصر ثم أطلق عليها اسم القاهرة فى القرن الرابع الهجرى (العاشر الميلادى).
ولقد شعر عمرو بالإهانة عندما قام الخليفة عثمان [رضى اللَّه عنه] بعد فترة قليلة من توليه الخلافة بعزله عن ولاية مصر وتولية عبد اللَّه بن سعد مكانه فاعتزل الحياة العامة مما أكد شعوره بالإهانة.