Dopo il ritiro dei Bizantinidall'Egitto , l'Esarcato d'Africa dichiarò la propria indipendenza.Sotto il suo esarca Gregorio Patrizio i suoi domini si estendevano dai confini dell'Egitto al Marocco.Abdullah ibn Sa'ad inviò gruppi di razziatori a ovest, ottenendo un considerevole bottino e incoraggiando Sa'ad a proporre una campagna per conquistare l'Esarcato.Uthman gli ha dato il permesso dopo averlo considerato nel Majlis al-Shura.Una forza di 10.000 soldati fu inviata come rinforzo.L'esercito Rashidun si radunò a Barqa in Cirenaica, e da lì marciò verso ovest, catturò Tripoli e poi avanzò verso Sufetula, la capitale di Gregorio.Nella battaglia di Sufetula, l'Esarcato fu sconfitto e Gregorio fu ucciso a causa della tattica superiore di Abdullah ibn Zubayr.Successivamente, il popolo del Nord Africa chiese la pace, accettando di pagare un tributo annuale.Invece di annettere il Nord Africa, i musulmani preferirono fare del Nord Africa uno stato vassallo.Quando fu pagato l'importo stabilito del tributo, le forze musulmane si ritirarono a Barqa.Dopo la Prima Fitna, la prima guerra civile islamica, le forze musulmane si ritirarono dal Nord Africa verso l'Egitto.Il califfato omayyade avrebbe poi reinvaso il Nord Africa nel 664.