پس از سقوط بابل به دست نیروهای راشدین در دسامبر ۶۴۰، عمرو بن عاص مدتی ارتش خود را در منطقه مستقر نگه داشت و با ارسال پیامی به خلیفه عمر از پیروزی خود خبر داد و اجازه ادامه فتح به سوی اسکندریه را درخواست کرد. این توقف به ارتش او استراحت بسیار مورد نیازش را نیز داد. در قسطنطنیه، امپراتور سالخورده و بیمار هراکلیوس با واکنش به آخرین پیروزی مسلمانان، چند هزار نیروی کمکی دیگر را از طریق دریای مدیترانه به مصر فرستاد. آن‌ها دستورات روشنی داشتند - اسکندریه را به هر قیمتی محافظت کنند. پس از پیاده شدن در پایتخت استان، این نیروهای کمکی و پادگان موجود اسکندریه، احتمالاً تحت فرماندهی تئودوروس، شروع به تقویت استحکامات شهر و گسترش به مواضع قابل دفاع در مسیر شهر کردند. گزارش‌هایی از این آماده‌سازی‌ها به عمرو در جنوب رسید. تقریباً در همان زمان، پیامی از عربستان با دستور خلیفه برای پیشروی و تصرف اسکندریه رسید. بنابراین، عمرو با ترک یک پادگان کوچک برای نگه داشتن بابل و تحت کنترل نگه داشتن منطقه ممفیس، به مردانش دستور داد اردوگاه را ترک کنند. ارتش ۱۲ هزار نفری مسلمان در فوریه ۶۴۱ به سمت شمال حرکت کرد.
مسلمانان با حرکت در امتداد حاشیه غربی دلتای نیل که بلافاصله در مجاورت آب و هوای بیابانی آشنا قرار داشت، مقاومت سبک رومیان در ترنوت و کوم شریک را پشت سر گذاشتند و سپس به سمت شمال غرب، دور از رودخانه، تغییر جهت دادند. پس از تصرف سولتیس، عمرو سپس در کیریاون، در فاصله تنها ۱۲ مایلی اسکندریه، پیروزی خونینی به دست آورد و نیروهای شکست‌خورده رومی را تا نزدیکی شرقی شهر تعقیب کرد. این راهپیمایی به سمت دریا تنها ۲۲ روز طول کشیده بود.
اسکندریه توسط اسکندر کبیر و جانشینان بطلمیوسی او در یک نوار نسبتاً باریک از زمین ساخته شده بود که از شمال به دریای مدیترانه و از جنوب به دریاچه ماریوت محدود می‌شد. از آنجا که مسیرهای اصلی حمل و نقل در شرق شهر به پایان می‌رسید، تنها راه واقعاً آسیب‌پذیر، مسیر شمال شرقی بود. مسلمانان خارج از محدوده سلاح اردو زدند و سپس برای نبرد مستقر شدند و به آرامی به سمت دیوارهای اخیراً تقویت‌شده اسکندریه پیشروی کردند. متأسفانه برای عمرو، چنین حرکت مقدماتی بی‌دقتی به توپچی‌های ماهر رومی اجازه داد تا واحدهای او را با شلیک پیاپی سنگ‌های بزرگ منجنیق مختل و پراکنده کنند. این بمباران عمرو و جنگجویانش را وادار کرد تا با اجتناب از پرتابه‌ها به اردوگاه بازگردند. چنین حملاتی با وقفه‌هایی ادامه یافت و در این وقفه‌ها مدافعان رومی به جای آن از شهر خارج می‌شدند و به ارتش مسلمان حمله می‌کردند و هدفشان عقب راندن آن و پایان دادن به محاصره بود. علیرغم خشونت و شایستگی مردانی که آن‌ها را اجرا می‌کردند، این تلاش‌ها به طور مداوم شکست خورد و در نهایت به داخل شهر رانده شدند.
در نقطه‌ای در طول ماه‌های اول اقدامات نامشخص، مدافعان علیه بخشی از جبهه که توسط قبیله عرب مهره نگهبانی می‌شد، خارج شدند و درگیری شدیدی آغاز شد. به نظر می‌رسد که نتیجه آن تساوی نامشخص بوده است، اما مهره مردی را از دست داد که سرش توسط رومیان بریده و برده شد و این باعث خشم اعراب شد. صبح روز بعد، همان اتفاق افتاد. یک افسر رومی، که احتمالاً توسط اقدامات روز قبل اعتماد به نفس پیدا کرده بود، به مهره حمله کرد، اما این بار نتیجه بسیار متفاوت بود. پس از کشته شدن در درگیری، سرش توسط جنگجویان عرب گرفته شد و به عنوان ابزار معامله برای بازگرداندن سر همرزمشان استفاده شد. پس از مذاکره کوتاهی، هر دو طرف تبادل کردند و خویشاوندان خود را با احترام به خاک سپردند.
در اوج تابستان، حدود دو ماه پس از اینکه عمرو ابتدا اردوگاه خود را برپا کرد، فرمانده قبیله سهمی به دلایلی که از آن اطلاعی نداریم، تصمیم گرفت آن را به جلو منتقل کند. با این حال، هنگامی که نیروهایش در حال حرکت بودند، مدافعان رومی فرصتی احساس کردند و یک حمله جسورانه سواره‌نظامی را ترتیب دادند که با این حال به راحتی دفع شد. یک دسته بی‌پروای سواره‌نظام مسلمان به تعقیب رومیان فراری پرداخت و در واقع قبل از اینکه مدافعان بتوانند دروازه‌ها را پشت سرشان ببندند، وارد شهر شدند. آن‌ها که به شدت در اقلیت بودند، درگیری شدیدی در کلیسای طلایی انجام دادند که در آن برخی از آن‌ها کشته شدند و بقیه از اسکندریه بیرون رانده شدند.
هراکلیوس که به طور مداوم با اسکندریه در تماس بود، به خوبی آگاه بود که مسلمانان در حال کسب تکانه هستند. او که نگران از دست دادن تمام مصر بود، ارتش مصممی را از سراسر آنچه از امپراتوری باقی مانده بود، همراه با تجهیزات و تدارکات جمع‌آوری کرد. دقیقاً قبل از اینکه این کاروان عظیم کمکی به رهبری امپراتور عازم شود، هراکلیوس در سن ۶۶ سالگی در قسطنطنیه درگذشت و پسران بزرگترش، کنستانتین سوم و هراکلوناس را به عنوان وارثان مشترک باقی گذاشت. این امر دوری از سیاست‌گذاری امپراتوری را آغاز کرد که در بدترین زمان ممکن به امپراتوری اجازه واکنش نمی‌داد. کنستانتین به عنوان امپراتور ارشد سعی کرد کنترل وضعیت به طور فزاینده‌ای وخیم در مصر را به دست گیرد. مرگ نابهنگام او تنها مدت کوتاهی بعد، این برنامه‌ها را به کلی منحرف کرد. اگر این به اندازه کافی بد نبود، برخی از ژنرال‌های بیزانسی، از جمله والنتینوس، به حمایت از پسر کنستانتین، کنستانس دوم، اسلحه برداشتند و معتقد بودند که مادر هراکلوناس، مارتینا، کنستانتین را مسموم کرده است. این مبارزه دودمانی تا اواخر ۶۴۱ به نتیجه نرسید و تضمین کرد که هیچ نیروی کمکی به اسکندریه فرستاده نخواهد شد.
سیاست‌بازی همچنین سربازان مدافع پایتخت مصر را آلوده کرد و باعث درگیری داخلی و از دست دادن گسترده روحیه شد. هنگامی که محاصره به ماه ششم خود کشیده شد و هیچ نشانه‌ای از پایان آن نبود، عمرو نامه‌ای از خلیفه دریافت کرد که او را به خاطر این همه تأخیر سرزنش می‌کرد. بنابراین، پس از مشورت با ژنرال‌هایش، عمرو اُباده بن صامت با تجربه را برای رهبری یک حمله انتخاب کرد. در اواخر اکتبر ۶۴۱، تمام ارتش مسلمان برای نماز ظهر جمع شدند و سپس برای نبرد مستقر شدند. سپس، تحت رهبری اُباده، نیروهای عمرو در نهایت با یورش به دروازه‌ای نزدیک کلیسای طلایی، اسکندریه را تصرف کردند.
از دستاوردهای مسلمانان در این نقطه - ۲۰ سال پس از هجرت - تصرف اسکندریه از نظر اهمیت در کنار رویدادهایی مانند یرموک و القادسیه قرار داشت. خلافت یک پایگاه دریایی ارزشمند را به دست آورد در حالی که قدرت دریایی روم را کاهش داد و سرزمینی با ثروت و فرهنگ عظیم را فتح کرد. شاید مهم‌تر از همه برای آینده، تصرف مصر به ارتش‌های اسلامی اجازه داد تا حتی بیشتر به سمت جنوب و غرب به آفریقا نفوذ کنند. ثروت، زیبایی و تجمل اسکندریه به یک اندازه اعراب و ژنرال آن‌ها را به دام انداخت، اما عمرو نمی‌توانست بدون اجازه خلیفه مقر فرماندهی خود را در آنجا قرار دهد. بنابراین، او یک فرستاده به مدینه فرستاد و از عمر پرسید که آیا می‌تواند در کلان‌شهر بماند یا خیر. متأسفانه برای فاتح مصر، یکی از خصوصیات متعدد حاکم راشدین، تحقیر و بی‌اعتمادی مطلق او به گستره‌های بزرگ آب، مانند نیل بود. تنها موردی که عمر به یکی از فرماندهانش - حاکمی از دمشق معروف به معاویه - اجازه داد یک عملیات دریایی را آغاز کند، کل نیرو نابود شده بود. بنابراین، عمر درخواست عمرو را رد کرد و توضیح داد: "من نمی‌خواهم مسلمانان در جایی سکونت کنند که زمستان یا تابستان بین من و آن‌ها قرار گیرد."
عمرو که ناامید شده بود، به سمت جنوب حرکت کرد و پایه‌های شهر جدید خود، اولین پایتخت مصر اسلامی، میصر الفسطاط - شهر چادرها، یا به اختصار فسطاط را بنا نهاد. فرماندار جدید کشور در ماه‌های بعد مشغول اداره جدیدترین قلمرو خلافت بود. با پایان یافتن سال ۶۴۱ و آغاز ۶۴۲، عمرو به حل اختلافات بین جنگجویان و مردم محلی پرداخت، بخش‌های قبلاً رها شده زیرساخت‌ها، از جمله کانال‌ها را احیا کرد و حتی به درخواست عمر، کمک‌های غذایی به مدینه قحطی‌زده فرستاد.
برای خاموش کردن هرگونه مقاومت باقی‌مانده در برابر حکومت مسلمانان، عمرو سه ستون به مناطق اطراف دمیاط، هلیوپولیس و فیوم فرستاد، در حالی که ستون چهارم اطمینان حاصل کرد که بقیه مصر سفلی مطیع هستند. همه آن‌ها زمان آسانی داشتند و تا اواسط ۶۴۲ بدون خونریزی وظیفه خود را انجام دادند.
عمرو بن عاص ماجراجو که مصر را محکم در اختیار داشت، توجه خود را به سمت پادشاهی نوبی مسیحی‌شده به نام ماکوریا در جنوب معطوف کرد. ماکوریا که توسط پادشاهی به نام قلیدوروت از ارگ بزرگش در دانقلا حکومت می‌شد، یک قدرت در حال ظهور و توسعه‌طلب در آفریقای زیرصحرایی بود. در واقع، پادشاه آن به تازگی رقیب سابق منطقه‌ای نوباتیا را ضمیمه کرده بود. جامعه‌ای باسواد با فرهنگ پویای خود، نوبیایی‌ها به عنوان جنگجویان سرسخت و خشن معروف بودند. به ویژه، شهرت آن‌ها در سوارکاری و تیراندازی در سراسر جهان مدیترانه شناخته شده بود.
در نقطه‌ای در طول تابستان سوزان آفریقایی ۶۴۲، عمرو پسرعموی خود عقبه بن نافع و ۲۰ هزار سواره‌نظام را به نوبیا فرستاد، جایی که آن‌ها به سرعت شروع به رنج بردن از دست ساکنان محلی کردند. تیراندازان مرگبار اما بدون زره ماکوریا - سواره و پیاده - که نتوانسته بودند در یک نبرد منظم در برابر مسلمانان مقاومت کنند، حملات مداوم چریکی را آغاز کردند که به تدریج قدرت عقبه را تحلیل بردند و سپس بدون آسیب به بیابان بازگشتند.
همانطور که ارتش اسلامی به عمق نوبیا پیشروی کرد و با حملات چریکی به تعداد و خشونت فزاینده‌ای روبرو شد، تیراندازان تیزبین ماکوریا اغلب به مهاجمان عرب فریاد می‌زدند: "دوست داری تیر را در کجای بدنت بگذارم؟" هنگامی که یکی از جنگجویان مسلمان با تردید به قسمتی از بدن خود اشاره می‌کرد، منابع ما می‌گویند که یک تیر واقعاً به آنجا برخورد می‌کرد و فرد مورد نظر را مجروح یا می‌کشت.
وقتی عقبه و نیروهای کاهش‌یافته‌اش در نهایت به پایتخت ماکوریا در دانقلا نزدیک شدند، ارتش کوچکتری متشکل از حدود ۱۰ هزار نفر را پیدا کردند که به دلیل حرکت‌های عقبه مجبور به دفاع از شهر مرکزی خود شده بودند. عقبه که مشتاق نابودی پتانسیل جنگی نوبیایی‌ها بود اکنون که همه آن‌ها را در یک مکان داشت، شروع به آرایش نیروهایش برای نبرد کرد. همانطور که پیشروی مسلمانان به سمت خط قلیدوروت آغاز شد، تقریباً بلافاصله با بارانی بی‌رحم از تیرهای ماکوریا که با دقت بالا به ارتش مهاجم برخورد می‌کرد، مورد اصابت قرار گرفت. حمله عقبه در همان ابتدا با تگرگ پرتابه‌ها متوقف شد و سربازانش که ۲۵۰ نفر از آن‌ها حداقل یک چشم خود را در نبرد از دست داده بودند، به شدت رنج بردند. عقبه که نمی‌توانست به تیراندازان نوبیایی نزدیک شود و به سرعت مردانش را به دلیل جراحات شدید از دست می‌داد، جنگجویانش را از میدان جنگ خارج کرد.
مسلمانان پس از این برای همیشه نوبیایی‌ها را "تیراندازان چشم" نامیدند، زیرا آن‌ها علاقه داشتند تیرها را با دقت مرگ‌باری به چشم دشمنانشان رها کنند. مسلمانان که تمایلی به ادامه چنین کارزار دشواری در سرزمینی که غنیمت یا زمین آینده کمی به آن‌ها وعده می‌داد نداشتند، به عقب‌نشینی ادامه دادند تا به فسطاط بازگشتند. اگرچه دقیقاً یک شکست قطعی نبود، اما ارتش خلافت پس از مدت ها شکست ناپذیر بودن شکست خورده بود.
پس از یک یا دو ماه استراحت و بازیابی قوا، عمرو در سپتامبر ۶۴۲ ارتش‌های خود را از اردوگاه‌های موقتشان جمع‌آوری کرد و شخصاً آن‌ها را به سمت غرب به صحرا رهبری کرد. پس از یک ماه راهپیمایی سخت، مسلمانان سرانجام به شهر رومی‌نشینی به نام برقه رسیدند که به دلیل نداشتن هیچگونه تمهیدات دفاعی، به سرعت تسلیم شد. این اولین اقدام در فتح اسلامی منطقه‌ای بود که امروزه مغرب نامیده می‌شود و دهه‌ها به طول انجامید. عمرو عقبه را مأمور کرد تا از ساحل به داخل سرزمین حرکت کند، جایی که او با موفقیت منطقه بیابانی خشک بین برقه و زاویله را بدون خشونت آرام کرد. جمعیت فقیر به سرعت ثابت کردند که قانون‌مدار و قابل اعتماد در پرداخت مالیات هستند، بنابراین عمرو فرمان داد بخشی از درآمدهای حاصل از کل منطقه فزان صرف کاهش فقر در آنجا شود.
سپس در بهار ۶۴۳، ارتش مسلمان به سمت شهر تحت حفاظت رومیان، طرابلس، پیشروی کرد و آن را محاصره نمود. عمرو اردوگاه خود را در بخش مرتفعی از زمین در شرق شهر برپا کرد و منتظر ماند، زیرا می‌دانست چنین سکونتگاه ساحلی می‌تواند برای مدت طولانی از طریق دریا تجهیز شود. با عدم وجود سلاح‌های محاصره‌ای، او همچنین توانایی کاهش استحکامات را نداشت. پس از دو ماه عدم فعالیت نسبی، هشت تن از جنگجویان عمرو به سمت غرب شهر برای شکار تاختند. وقتی این شکارچیان در حدود ظهر راه بازگشت را در پیش گرفتند، گرمای شدید روز باعث شد آن‌ها در امتداد ساحل بازگردند. ناگهان، به مرز غربی طرابلس رسیدند، جایی که دیوار شهر به دریا می‌رسید، و متوجه شدند که این بخش تنها به‌صورت محدود محافظت می‌شود. در نمایشی از شجاعت یا حماقت، این هشت فرصت‌طلب جسور از جناح آسیب‌پذیر طرابلس استفاده کردند تا راه خود را به داخل شهر باز کنند. قبل از اینکه مدافعان حتی متوجه شوند چه اتفاقی در حال رخ دادن است، گروه مسلمان به مرکز شهر رسید و شروع به کشتن دشمنان کرد.
چنین خشونت غیرمنتظره‌ای موجی از وحشت شدید را در داخل شهر، هم در میان غیرنظامیان و هم در میان نیروهای مدافع طرابلس، ایجاد کرد. در واقع، تعداد زیادی از سربازان مسلح داخل شهر باور داشتند که یک گروه بزرگ دشمن به نحوی وارد شهر شده است و به همین دلیل، به تعدادی از کشتی‌های لنگرانداخته در بندر پناه بردند. عمرو از هرج و مرج داخل شهر مطلع شد و بنابراین به سرعت شروع به بهره‌برداری از این ضعف کرد. او با عجله جنگجویان خود را آرایش داد و فرمانده عرب دستور یک حمله تمام‌عیار برای بالا رفتن از دیوارهای ضعیف‌شده طرابلس را صادر کرد. در یک اقدام دیگر که هیچ جزئیاتی از آن باقی نمانده است، مسلمانان موفق شدند داخل شهر شوند و به پیشقراولان هشت‌نفره خود بپیوندند. مدافعان رومی که تمایلی به ادامه جنگ نداشتند، هرچه می‌توانستند با خود برداشتند و با کشتی‌ها شهر را ترک کردند و طرابلس را به ارتش عمرو واگذار کردند.
در حالی که بیشتر ارتش مدتی در شهر ماندند، فاتح مصر یک دسته سریع سواره‌نظام را حدود ۴۰ مایل به سمت غرب فرستاد، جایی که جمعیت شهر سبراته هنوز بی‌خیال بودند. آن‌ها شایعاتی درباره درگیری‌های شهرهای همسایه شنیده بودند، اما مدت‌ها طول می‌کشید تا جنگ به آن‌ها برسد، اگر اصلاً می‌رسید. صبح روز بعد، نگهبانان رومی سبراته دروازه‌های شهر خود را باز کردند و جمعیت شروع به بردن حیوانات برای چرا کردند. متأسفانه برای آن‌ها، در همین لحظه بود که واحد سواره‌نظام اسلامی کاملاً غافلگیرکننده حمله کرد، از دروازه‌ها گذشت، بیشتر نیروهای مدافع را کشت و شهر را غارت کرد. پس از انجام این کار، آن‌ها به طرابلس بازگشتند.
عمرو که موفق شده بود، مشتاق بیشتر بود و با اشتیاق نامه‌ای دیگر به خلیفه عثمان نوشت که هم حاوی خبرهای خوب پیروزی و هم درخواست ادامه فتوحاتش بود. این درخواست رد شد، زیرا خلیفه نگران گسترش بیش از حد نیروهایش بود. و این بار هیچ راه گریز یا حیله هوشمندانه‌ای وجود نداشت که عمرو بتواند از فرمان عمر عبور کند و کارزار بی‌امان خود را ادامه دهد. بنابراین، پس از اجازه دادن به ارتشش برای مدتی در طرابلس استراحت کند، عمرو به فسطاط بازگشت و در آنجا ماند و به آرامی حوزه مصر خود را اداره کرد و با زمزمه‌های شورش آینده برخورد کرد.
اگرچه عمر بقیه آفریقای بیزانسی را موقتاً در امان گذاشته بود، اما این وضعیت دوام نمی‌آورد. با این حال، در حالی که نبرد در شمال آفریقا در حال پایان یافتن بود، وضعیت در جبهه ایرانی دوباره در حال گرم شدن بود. پیروزی پیروزی‌های مسلمانان در نهاوند در سال ۶۴۲ در نهایت پشت امپراتوری ساسانی را شکست و قلمروهای آن در غرب مانع زاگرس را عملاً بی‌دفاع در برابر الحاق به خلافت کرد. ناآگاه از خلیفه، این درگیری شدید همچنین عواقب غیرمنتظره‌ای برای او به‌طور شخصی داشت.
یک اتفاق غیرمنتظره دیگر نیز به جهان اسلام در حال صعود، و به ویژه یکی از جدیدترین دستاوردهای آن - مصر - توسط بیزانسی‌ها که تازه از جنگ داخلی خود خارج شده بودند، پرتاب شد. این امر فاتح عرب نیل - عمرو بن عاص - را به اجبار به مرکز رویدادهای جهانی بازگرداند.
در اواخر ۶۴۳، اندکی پس از بازگشت عمرو از لشکرکشی خود علیه به اصطلاح پنتاپولیس، فرماندار مصر برای ملاقات با عمر به مدینه بازگشت، کسی که از قبل رابطه‌ای تا حدودی تنش‌زا با او داشت. عمرو که مورد اعتماد خلیفه نبود، از همان ابتدا با استقبالی سرد مواجه شد. تنش بین این دو مرد به این دلیل تشدید شد که عمر که همیشه از طریق یک شبکه جاسوسی داخلی بر فرمانداران خود نظارت دقیق داشت، عمرو را به اختلاس ناعادلانه ثروت مصر متهم می‌کرد. بنابراین، وقتی عمرو به استان خود بازگشت، خلیفه یک بازرس مورد اعتماد - محمد بن مسلمه - را برای ارزیابی دارایی‌های عمرو فرستاد. عمرو حساب دارایی‌های خود را ارائه داد و مقصر شناخته شد که بیش از حد گرفته است. مازاد آن ضبط و به مدینه بازگردانده شد.
این پایان مداخلات مداوم خلیفه نبود. مدت کوتاهی پس از آن، عمر که از درآمدهای ناامیدکننده وارد شده به خزانه از مصر ناراضی بود، بحث داغی را با عمرو از طریق نامه انجام داد. پس از اینکه این بحث به بن‌بست رسید، یک قبطی به مدینه فرستاده شد تا خلیفه را از وضعیت مالی استانش مطلع کند. او صریحاً به عمر گفت که حاکمان قبلی مصر قبل از گرفتن هر چیزی از آن، به رفاه زمین توجه کرده‌اند، در حالی که فرمانداران مسلمان فقط می‌گیرند. در پاسخ، عمر در اواخر ۶۴۴ مصر را به دو ناحیه اداری جداگانه تقسیم کرد، به عمرو مصر سفلی را داد تا از فسطاط حکومت کند، در حالی که مصر علیا توسط عبدالله بن سعد بن ابی سرح، برادر رضاعی عثمان، از فیوم اداره می‌شد. قابل پیش‌بینی بود که عمرو یک بار دیگر از این کاهش عمدی اختیاراتش خشمگین شد.
در مدینه یک توطئه مرگبار شکل گرفته بود که حول هرمزان می‌چرخید، کسی که به اسلام گرویده بود و از تجربه گسترده خود در اداره و حکومت ساسانی استفاده کرد تا به یکی از مشاوران کلیدی عمر تبدیل شود. با این وجود، این نجیب‌زاده ایرانی هرگز آسیب وارد شده به وطنش را فراموش نکرد. به نظر می‌رسد هرمزان با فیروز، یک سرباز ساسانی که پس از قادسیه یا نهاوند به بردگی گرفته شده و به پایتخت خلافت آورده شده بود، ارتباط برقرار کرد و در نوامبر ۶۴۴ فیروز عمر را با چاقو زد. خلیفه دوم قبل از مرگ سه روز پس از آن، یک شورای شش نفره منصوب کرد تا جانشین او را از میان خود انتخاب کنند. پس از بحث عمیق، آن‌ها تصمیم گرفتند که عثمان به عنوان سومین خلیفه راشدین انتخاب شود. شایان ذکر است که در حالی که اسلام سنی عثمان را یکی از خلفای راشدین می‌داند، مسلمانان شیعه معتقدند این انتخابات اصلاً نباید اتفاق می‌افتاد و علی باید نفر بعدی می‌بود.
کمی بعد، عمرو بن عاص به ملاقات عثمان رفت تا برای برکناری همکار مصری علیایش لابی کند. خلیفه جدید به طور قطعی امتناع کرد و باعث شد عمرو اعلام کند تا زمانی که عبدالله بن سعد برکنار نشود، به مصر بازنخواهد گشت. در پاسخ به این تهدید، عثمان برادر رضاعی خود را به عنوان فرماندار کل مصر منصوب کرد، که اختلاف بین این دو مرد را عمیق‌تر کرد.
رومیان در مصر از سیاست‌های عمرو راضی نبودند، اما تلاش‌های عبدالله برای افزایش درآمدهای استان حتی کمتر محبوب بود. اسکندریه به ویژه بار اصلی این میل جدید به درآمد را تحمل می‌کرد، که باعث شد جمعیت آشوبگر معروف آن اقدامات مهم انجام دهند. یک گروه از رومیان برجسته پیام‌هایی به امپراتور جدید کنستانس دوم فرستادند. این نامه‌ها به بیان جنایات حکومت مسلمانان و مالیات جزیه آن‌ها پرداخت، اما همچنین اشاره کرد که عبدالله دفاع از قلمرو نیل را به وضعیت اسفناکی سقوط داده است و شهر تنها توسط هزار نفر سرباز محافظت می‌شود و به راحتی قابل تصرف است.
کنستانس که فرصتی برای بازپس‌گیری کنترل مصر و التیام زخمی که از دست دادن آن به امپراتوری و غرورش وارد کرده بود مشاهده کرد، شروع به جمع‌آوری مخفیانه یک نیروی ضربتی بزرگ متشکل از ۳۰۰ کشتی و هزاران سرباز کرد که فرماندهی آن را به یک خواجه به نام مانوئل سپرد. ناوگان کنستانس پس از تقریباً یک سال آماده شد. از آنجا که امپراتوری کاهش‌یافته بیزانس هنوز قدرت دریایی مسلط در مدیترانه بود - خلافت هنوز هیچ توانایی دریایی توسعه نداده بود - هیچ چیزی نمی‌توانست مانع از ورود غیرمنتظره این ناوگان به بندر اسکندریه در اوایل ۶۴۶ شود.
همانطور که همدردان رومی پیش‌بینی کرده بودند، پادگان هزار نفری مسلمانان دفاع مناسبی در برابر این حمله غافلگیرکننده از دریا نبود. وقتی نیروهای رومی تقریباً بدون مقاومت پیاده شدند، جمعیت اسکندریه همزمان بر علیه اعراب اشغالگر شورش کردند. بیشتر پادگان شهر در درگیری کوتاهی که پس از آن رخ داد کشته شدند. با این حال، در حالی که ارتش مهاجم شروع به ویرانی اطراف اسکندریه کرد، برخی از مسلمانانی که فرار کردند به فسطاط سفر کردند و فرماندار را از آنچه اتفاق می افتاد مطلع کردند.
عبدالله بن سعد حتی فرصت واکنش نداشت. مسلمانان مصر که به توانایی رزمی نایب جدید خود اعتماد نداشتند، هیئتی به نزد خلیفه عثمان فرستادند و از او خواستند عمرو را بازگرداند تا بتواند بحران را پایان دهد. عثمان که می‌دانست عمرو هم مردی با استعداد نظامی و مصممی است و هم مورد ترس رومیان، زبانش را گاز گرفت و از عمرو خواست تا پست خود را بازپس گیرد. عمرو که زمانی رومیان را فتح کرده بود، بدون اتلاف وقت به سرعت به سمت فسطاط حرکت کرد تا به تقلید از دستاورد قبلی خود بپردازد. با ورود او، روحیه جنگجویان اسلام به طور قابل توجهی افزایش یافت و آن‌ها با اشتیاق برای جنگ آماده شدند، در حالی که عمرو شروع به برنامه‌ریزی کرد.
با اطلاع از جاسوسان و عوامل خود که رومیان به آرامی از اسکندریه به سمت فسطاط پیشروی می‌کنند، بسیاری از افسران بی‌پروای عمرو اصرار داشتند که فرمانده‌شان به دشمن حمله کند و آن‌ها را درون آن کلان‌شهر مرموز مدیترانه‌ای محصور نماید قبل از آنکه تمام مصر علیه حکومت مسلمانان شورش کند. عمرو با این ارزیابی موافق نبود، چرا که معتقد بود این پیشروی، خطوط تأمین و ارتباطات رومیان را تا حد کشش کامل خواهد کشید. مانوئل و سپاهش تحت نظارت نزدیک خبرچینان عمرو حرکت می‌کردند که مدام موقعیت و قدرت رومیان را گزارش می‌دادند. نیروهای زمینی از کرانه شرقی نیل بالا می‌رفتند در حالی که ناوگان بزرگی از کشتی‌های جنگی پشتیبان به موازات آن‌ها در خود رودخانه در حرکت بودند. بی‌نظمی بیزانسی‌ها تقریباً بلافاصله مشکلاتی ایجاد کرد. سربازان رومی از شهری به شهر دیگر می‌رفتند و مردم از رفتار آن‌ها ناراضی بودند. وقتی مانوئل به نقطه میانی بین اسکندریه و فسطاط نزدیک شد، عمرو با ۱۵ هزار جنگجوی خود ضدحمله را آغاز کرد و مستقیماً به سمت برخورد با رومیان حرکت نمود. سرانجام دو سپاه در نزدیکی شهر بزرگی به نام نیکیو یا ناقیوس با یکدیگر تماس پیدا کردند. پس از استراحت شبانه در اردوگاه‌های مربوطه، رومیان و مسلمانان در زمین‌های کشت‌شده، هموار و بی‌عیب جنوب نیکیو صف‌آرایی کردند.
جناح چپ عمرو - یک هنگ سواره تحت فرمان شریک بن سمیه - در کنار رود نیل مستقر شد، همانند جناح راست رومیان. علاوه بر سازماندهی در صفوف منظم، تعداد زیادی از کمانداران رومی نیز بر کشتی‌های رودخانه سوار شدند. هنگامی که آماده‌سازی‌هایش برای نبرد کامل شد، مانوئل به نیروهای زمینی بیزانس دستور داد تا در محدوده مؤثر تیررس کمان‌ها پیشروی کنند، سپس توقف نموده و بارانی ویرانگر از تیرها بر مواضع مسلمانان فرو ریختند. در رودخانه، مانوئل یک حیله هوشمندانه تدارک دیده بود. کشتی‌هایش به حرکت ادامه دادند تا از جناح عمرو گذشتند، در این نقطه کمانداران روی عرشه نیز به مسلمانان از جناح حمله کردند. مردان عمرو از قبل درگیر مقابله با آتش بودند، بنابراین از بمباران چندجهتی به شدت آسیب دیدند. به ویژه هنگ سمیه که نزدیک‌ترین موقعیت را به رودخانه داشت، تقریباً به طور کامل نابود شد، اما حتی عمرو نیز اسبی از زیر پایش زخمی شد. با این وجود، علیرغم این مجازات، مسلمانان حاضر نبودند میدان نبرد را تسلیم کنند و بنابراین با پایداری قابل توجهی طوفان را تحمل کردند. وقتی مانوئل اعتقاد یافت که دشمن به اندازه کافی تضعیف شده، کشتی‌های جناحی را فراخواند و نیروهای روی عرشه را در رده‌های پشت سپاه اصلی قرار داد، سپس حمله دیگری با تیرها علیه خطوط مسلمانان آغاز کرد. لحظه‌ای پس از آنکه ژنرال خواجه بیزانسی دستور توقف آتش اولیه را صادر کرد، به پیاده‌نظامش فرمان داد تا به محدوده نیزه و شمشیر پیشروی کنند.
اگرچه ارتش‌های اولیه مسلمان عموماً به عنوان نیروهایی که در این نوع درگیری‌های تن به تن راحت‌تر بودند به تصویر کشیده شده‌اند، اما سربازان رومی با خشونت قابل توجهی به سپاه خسته عمرو ضربه زدند و خطوط از قبل متزلزل آن‌ها را در هم شکستند. هنگ سمیه که اصلی‌ترین ضربه حمله موشکی آبی مانوئل را تحمل کرده بود، در واقع گسیخته و فرار کرد. عمرو عجولانه باقی‌مانده مردانش را از حمله رومیان دور کرد و تنها در فاصله کوتاهی توقف نمود تا به بهترین شکل ممکن تجدید قوا کند. اما مانوئل که گمان می‌کرد مسلمانان شکست خورده‌اند، پیشروی نکرد و دشمن را تمام نکرد، بلکه فقط در جای خود منتظر ماند. پس از مکثی کوتاه و عجیب در نبرد، یک قهرمان رومی با لباس‌های فاخر، زرهی منقش به طلا پوشیده، به فضای باز بین دو سپاه آمد و مسلمانان را به مبارزه تن به تن دعوت کرد. این به آن‌ها فرصتی می‌داد تا نفسی تازه کنند، تجدید قوا کرده و سازماندهی شوند. بنابراین، یکی از مبارزان مورد علاقه عمرو - عربی به نام هومل - پیشنهاد رومی را پذیرفت و به استقبال جنگجوی دشمن رفت. در حالی که باقی‌مانده هر دو سپاه شاهد بودند، قهرمانان آن‌ها ابتدا با نیزه به هم حمله کردند و هیچ یک از مبارزان نتوانست ضربه قاطعی وارد کند. پس از گذشت مدتی، قهرمانان نیزه‌ها را انداخته و با شمشیر و سپر به هم حمله کردند، اما باز هم هیچ یک بر دیگری برتری نیافت. این وضع ادامه یافت تا اینکه دوئلیست رومی که جثه بزرگتری داشت، توانست هومل را خلع سلاح کرده و با چند ضربه شدید به شدت زخمی کند. در حالی که رومی تنومند قصد داشت کار هومل را تمام کند، قهرمان عربی خنجر کوتاه خود را کشید و با سرعتی حیرت‌آور آن را در گلوی حریف غافلش فرو برد. اگرچه هومل به سختی توانست دوئل را ببرد، اما چند روز بعد بر اثر جراحاتش درگذشت که موجب تاسف عمرو شد. این مبارزه سنتی تن به تن به ژنرال مسلمان فرصت داد تا سپاهش را منظم کند و تا زمان پیروزی هومل، عمرو آماده بود - حتی هنگ فراری سمیه به میدان نبرد بازگشت و صف آرایی کرد. وقتی کل سپاه مسلمان آماده شد، حمله کرده و درگیر نبرد تن به تن فرسایشی با نیروهای مانوئل شدند، نوعی نبرد که برای آن بسیار مناسب‌تر بودند. پس از چند ساعت مقاومت رومیان، سربازان خواجه شکسته و فرار کردند و تا اسکندریه تعقیب و کشته شدند. عمرو چندین منجنیق آورده و سنگ‌های بزرگی به سمت شهر سرکش پرتاب کرد که توپچیان شهر نیز پاسخ دادند. با این حال، دفاعیات تحت این بمباران استوار باقی ماند، تا اینکه یکی از دربانان - ابن بسانه - پیشنهاد داد در ازای ایمنی خود، خانواده و اموالش، اجازه دهد نیروهای عمرو وارد شهر شوند، شرایطی که فرمانده مسلمان با آن موافق بود. بنابراین، در نقطه‌ای از میانه سال ۶۴۶، دروازه‌های اسکندریه گشوده شد و ارتش اسلام به داخل ریخت. هر واحد رومی که در برابر این تهاجم مقاومت می‌کرد، به سرعت سرکوب می‌شد و حتی نیروهای کمکی که برای پرکردن شکاف می‌آمدند نیز عقب رانده شدند.
وقتی شهر شورشی شروع به غارت شدن کرد، سربازان امپراتوری که زنده مانده بودند به کشتی‌هایشان عقب نشینی کرده و رفتند. قبل از آنکه اعراب انتقام‌جو بتوانند واقعاً در آن کلان‌شهر باستانی مدیترانه‌ای و ساکنان شکست‌خورده‌اش ویرانی به بار آورند، یک مسلمان ناشناس نزد عمرو آمد و از او خواست تا خشونت را متوقف کند. اگرچه فاتح مصر به هیچ وجه ذاتاً فردی بخشنده نبود، اما سخنان همکیشش چنان تاثیری داشت که عمرو بلافاصله دستور توقف خصومت‌ها را صادر کرد. درست در همان نقطه که این فرمان اعلام شد، مسجدی ساخته شد که به "مسجد رحمت" معروف گشت. با این حال، تعداد زیادی از رومیان از جمله مانوئل در نبرد کشته شدند و شورش سرکوب گردید. در پی محاصره دوم اسکندریه، عمرو دیوارهای شهر را ویران کرد و به قول خودش شهر را "مانند خانه یک زن زناکار، از همه طرف قابل دسترسی" ساخت. غفلت از دفاع مصر نیز با تقسیم جدید نیروهای نظامی مسلمان به چهار بخش جبران شد - دو بخش در فسطاط، و یک بخش در اسکندریه و یک بخش در ساحل شمالی که در صورت لزوم جابجا می‌شدند. همچنین هر شش ماه یکبار چرخش و تعویض نیروها انجام می‌گرفت. عمرو بن العاص نه تنها مصر را در شرایط دشوار فتح و بازفتح کرده بود، بلکه پایه‌های حکومتی را بنا نهاده بود که هژمونی مسلمانان بر این کشور حاصلخیز را تضمین می‌کرد. به همین دلیل، عمرو به خوبی انتظار پاداش از عثمان را داشت، اما قرار بود ناامید شود.
عثمان می‌خواست برادر مالیات‌ستاندنش آن موقعیت پرمنفعت را اشغال کند، اما آگاه بود که عمرو احتمالاً مستحق پاداشی برای اقداماتش است. بنابراین، با احضار فاتح به محل اقامتش، از او پرسید که آیا مایل است فرماندهی نظامی مصر را حفظ کند در حالی که عبدالله بن سعد اداره امور غیرنظامی را بر عهده بگیرد. عمرو با طعنه‌ای هوشمندانه پاسخ داد: "در آن صورت من مانند مردی خواهم بود که شاخ‌های گاو را نگه داشته در حالی که دیگری آن را می‌دوشد." برای باقی دوران خلافت عثمان، عمرو کینه‌توزی شدیدی داشت و حتی به طور علنی با او مخالفت می‌کرد. این رنجش متقابل در آینده نزدیک پیامدهای جدی برای تاریخ اسلام داشت.
