Miután a bizánciak kivonultakEgyiptomból , Afrika Exarchátusa kikiáltotta függetlenségét.Exarchája, Patrícius Gergely uralma Egyiptom határaitól Marokkóig terjedt.Abdullah ibn Sa'ad portyázó csapatokat küldött nyugatra, ami jelentős zsákmányt eredményezett, és arra ösztönözte Szaádat, hogy javasoljon kampányt az exarchátus meghódítására.Uthman engedélyt adott neki, miután megvizsgálta a Majlis al-Shurában.Erősítésként 10 000 katonából álló haderőt küldtek.A Rashidun sereg a cirenaicai Barkában gyülekezett, és onnan nyugatra vonultak, elfoglalták Tripolit, majd Szufetulába, Gergely fővárosába nyomultak.A szufetulai csatában az exarchátus vereséget szenvedett, és Gergely meghalt Abdullah ibn Zubayr kiváló taktikájának köszönhetően.Ezt követően Észak-Afrika népe pert indított a béke érdekében, és beleegyezett, hogy éves adót fizet.A muszlimok Észak-Afrika annektálása helyett inkább vazallus állammá tették Észak-Afrikát.Amikor az adó előírt összegét kifizették, a muszlim csapatok visszavonultak Barkába.Az első Fitna, az első iszlám polgárháború után a muszlim erők kivonultak Észak-Afrikából Egyiptomba.Az Omajjád kalifátus később 664-ben újra megtámadta Észak-Afrikát.