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

ولما تم التعاهد بين المسلمين والقبط هاجر جميع من كان بين هؤلاء من الروم ملتجئين إلى الإسكندرية، أما عمرو فعزم على النزول على الإسكندرية، وكانت محصنة تحصينا عظيما، وبها كثير من العسكر، فأمر عسكره بالرحيل إليها، فبينما هم يحملون للمسير وإذا بعمرو قد أخبر بأن زوج يمام قد باض على خيمته وأشرف على الفقس، فأمر عمرو بترك المخيمة قائمة إلى حين رجوعه من فتوح الإسكندرية، ثم سار قاصدا هذه المدينة، فحاصرها المسلمون أشهرا وهم لا يتمكنون من فتحها لشدة تحصينها، ثم ضيق عمرو الحصار عليها حتى التزم المحاصرون بعقد الصلح بعد مدافعة شديدة، فسلموا المدينة بعد حصارها أربعة عشر شهرا، فدخل عمرو مدينة الإسكندرية في أول يوم جمعة من شهر المحرم سنة 20 هجرية وقت صلاة الجمعة، ثم كتب لأمير المؤمنين عمر بن الخطاب يخبره بفتوحها وما تحتوي عليه، فكتب إليه عمر يهنئه بالظفر، وولاه عاملا على الديار المصرية، فوضع الحرس الكافي في الإسكندرية، ورجع إلى الموضع الذي كان ترك فيه خيمته وعسكر هناك بجيوشه على شاطئ النيل، فبنت العسكر في أول الأمر حول الخيمة أكواخا صغيرة، ثم شيدت الأمراء ورؤساء الجيوش قصورا مشيدة، فتكون من مجموع هذه المباني مدينة عظيمة سميت بالفسطاط، ومعناه الخيمة؛ حفظا لذكر الحادثة التي كانت سببا في تأسيسها، فجعلها عمرو عاصمة مصر، واتخذها مركزا لإقامته، وبنى بها جامعه الموجود باسمه في مصر العتيقة الآن، وتفرغ حينئذ لترتيب الحكومة، فقسم مصر إلى مقاطعات، وجعل على الإسكندرية المقوقس، وعلى الوجه القبلي عبد الله بن سعد بن أبي سرح، وتولى بنفسه صلات خراجها، وكان قد جعل على كل فرد من الأهالي دينارين جزية، خلا الشيوخ والنساء ومن لم يبلغ الحلم، فجبى من الأموال سنويا 12 مليون دينار، وقد أمره عمر بن الخطاب رضي الله عنه بأن يحفر خليجا من الفسطاط إلى البحر الأحمر لسهولة النقل إلى مكة والمدينة، فحفره وسماه خليج أمير المؤمنين، ولم يزل عاملا على مصر حتى عزله عثمان بن عفان سنة 26 هجرية، وولى مكانه عبد الله بن أبي سرح، فثقل الضرائب على الأهالي حتى وصلت إلى 14 مليون دينار سنويا، ثم تولى عليها قيس بن سعد ثم محمد بن أبي بكر من قبل علي بن أبي طالب رضي الله عنه، ثم عاد إليها عمرو سنة 38 هجرية من قبل معاوية ، فلم يزل واليا عليها حتى مات سنة 43 هجرية.