BizanslılarınMısır'dan çekilmesinin ardından Afrika Eksarhlığı bağımsızlığını ilan etti.Valisi Patrici Gregory'nin yönetimi altında hakimiyet alanı Mısır sınırlarından Fas'a kadar uzanıyordu.Abdullah ibn Sa'ad batıya baskın ekipleri göndererek önemli miktarda ganimet elde etti ve Sa'ad'ı Eksarhlığı fethetmek için bir kampanya önermeye teşvik etti.Osman bunu Meclis-i Şura'da değerlendirdikten sonra ona izin verdi.Takviye olarak 10.000 asker gönderildi.Raşidun ordusu Sirenayka'daki Barka'da toplandı ve oradan batıya doğru yürüdüler, Trablus'u ele geçirdiler ve ardından Gregory'nin başkenti Sufetula'ya ilerlediler.Sufetula Muharebesi'nde Abdullah ibn Zübeyr'in üstün taktiği nedeniyle Eksarhlık mağlup edildi ve Gregory öldürüldü.Daha sonra Kuzey Afrika halkı yıllık haraç ödemeyi kabul ederek barış talebinde bulundu.Müslümanlar, Kuzey Afrika'yı ilhak etmek yerine, Kuzey Afrika'yı vasal bir devlet haline getirmeyi tercih ettiler.Haracın öngörülen miktarı ödenince Müslüman güçler Barka'ya çekildi.İlk İslam iç savaşı olan Birinci Fitne'nin ardından Müslüman güçler Kuzey Afrika'dan Mısır'a çekildi.Emevi Halifeliği daha sonra 664'te Kuzey Afrika'yı yeniden işgal edecekti.