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