Na de terugtrekking van de Byzantijnen uitEgypte riep het Exarchaat van Afrika zijn onafhankelijkheid uit.Onder zijn exarch, Gregorius de Patriciër, strekte zijn heerschappij zich uit van de grenzen van Egypte tot Marokko.Abdullah ibn Sa'ad stuurde overvallers naar het westen, wat resulteerde in een aanzienlijke buit en Sa'ad aanmoedigde een campagne voor te stellen om het Exarchaat te veroveren.Uthman gaf hem toestemming nadat hij dit in de Majlis al-Shura had overwogen.Een troepenmacht van 10.000 soldaten werd ter versterking gestuurd.Het Rashidun-leger verzamelde zich in Barqa in Cyrenaica, en van daaruit marcheerden ze naar het westen, veroverden Tripoli en rukten vervolgens op naar Sufetula, de hoofdstad van Gregory.In de Slag bij Sufetula werd het Exarchaat verslagen en werd Gregory gedood vanwege de superieure tactiek van Abdullah ibn Zubayr.Daarna klaagde het volk van Noord-Afrika om vrede en stemde ermee in een jaarlijks eerbetoon te betalen.In plaats van Noord-Afrika te annexeren, gaven de moslims er de voorkeur aan om van Noord-Afrika een vazalstaat te maken.Toen het vastgestelde bedrag van het eerbetoon was betaald, trokken de moslimtroepen zich terug naar Barqa.Na de Eerste Fitna, de eerste islamitische burgeroorlog, trokken moslimtroepen zich terug uit Noord-Afrika naar Egypte.Het Umayyad-kalifaat zou later in 664 Noord-Afrika opnieuw binnenvallen.