Nach dem Rückzug der Byzantiner ausÄgypten erklärte das Exarchat Afrika seine Unabhängigkeit.Unter seinem Exarchen Gregor dem Patrizier erstreckten sich seine Herrschaftsgebiete von den Grenzen Ägyptens bis nach Marokko.Abdullah ibn Sa'ad sandte Razzien in den Westen, was zu beträchtlicher Beute führte und Sa'ad ermutigte, einen Feldzug zur Eroberung des Exarchats vorzuschlagen.Uthman gab ihm die Erlaubnis, nachdem er darüber im Majlis al-Shura nachgedacht hatte.Als Verstärkung wurde eine Truppe von 10.000 Soldaten entsandt.Die Rashidun-Armee versammelte sich in Barqa in der Kyrenaika, marschierte von dort nach Westen, eroberte Tripolis und rückte dann nach Sufetula, Gregors Hauptstadt, vor.In der Schlacht von Sufetula wurde das Exarchat besiegt und Gregor wurde aufgrund der überlegenen Taktik von Abdullah ibn Zubayr getötet.Danach baten die Menschen Nordafrikas um Frieden und stimmten der Zahlung eines jährlichen Tributs zu.Anstatt Nordafrika zu annektieren, wollten die Muslime Nordafrika lieber zu einem Vasallenstaat machen.Als der festgelegte Tributbetrag gezahlt war, zogen sich die muslimischen Streitkräfte nach Barqa zurück.Nach der Ersten Fitna, dem ersten islamischen Bürgerkrieg, zogen sich muslimische Streitkräfte aus Nordafrika nach Ägypten zurück.Das Umayyaden-Kalifat fiel später im Jahr 664 erneut in Nordafrika ein.