Nel frattempo anche l’Africa dovette fronteggiare una nuova minaccia, quella degli Arabi che tra il 634 e il 642 avevano conquistato Siria ed Egitto. La conquista islamica della Siria aveva cagionato l’arrivo in Africa di molti rifugiati dalla Siria, tra cui molti monofisiti. L’imperatore Costantino III, informato dal prefetto e dal vescovo di Cartagine dei sospetti che i monofisiti stessero cercando di fare proselitismo in Africa, ordinò che il clero monofisita avrebbe dovuto essere privato dei loro beni e confinato in monasteri cattolici. In seguito alla morte di Costantino III, tuttavia, i suoi successori adottarono una politica di compromesso con i monofisiti, riprendendo la dottrina del monotelismo introdotta da Eraclio nel 638. Nel novembre del 641 arrivò da Costantinopoli l’ordine di fermare ogni persecuzione di monofisiti a Cartagine e di rilasciare tutti i detenuti. Tuttavia il prefetto di Cartagine, Giorgio, rifiutò di eseguire l’ordine ordinando ai governatori provinciali di fare lo stesso. Fu poi condotto a Costantinopoli per rispondere alla sua condotta ma ciò non pose fine al dissidio religioso tra Costantinopoli e le province africane.
Nel frattempo gli Arabi intorno al 641-642 avevano completato la conquista dell’Egitto. Nel 642/643 le città di Oea e Sabratha furono saccheggiate dagli Arabi di Amr. Nel frattempo il governatore militare dell’Africa imperiale, Gregorio, si era rivoltato separando l’Africa dal governo centrale arrivando addirittura a usurpare il titolo imperiale autoproclamandosi imperatore. Gregorio ottenne l’appoggio non solo delle tribù maure e dei provinciali ma anche del clero cattolico ostile al monotelismo imposto dal nuovo imperatore Costante II. Nel 646 i vescovi africani di Numidia, Byzacena, Mauritania e Proconsolare avevano condannato il monotelismo come eretico e videro con favore l’usurpazione di Gregorio in quanto un usurpatore cattolico era pur sempre da preferire a un imperatore eretico. Nel 647 il governatore ribelle dovette fronteggiare l’invasione degli Arabi, i quali lo sconfissero e lo uccisero. Gli Arabi accettarono di ritirarsi in Cirenaica solo nel 648, dopo che l’esarcato d’Africa accettò di pagare loro un tributo.
Le fonti islamiche riferiscono che successivamente Costante II pretese che le province africane pagassero al governo centrale una tassa pari al tributo (di trecento quintali d’oro) pagato agli Arabi, ma le autorità reggenti l’Esarcato rifiutarono la richiesta. Ciò ebbe probabilmente luogo nel periodo in cui l’Imperatore aveva lasciato Costantinopoli per porre la residenza imperiale a Siracusa in Sicilia, con lo scopo probabile di contendere agli Arabi il controllo del Mediterraneo occidentale. Al-Tabari riporta che i funzionari che respinsero la richiesta erano molteplici e che furono per punizione imprigionati dal delegato dell’Imperatore, ma furono in seguito liberati da alcuni dei loro associati che si rivoltarono contro il delegato. Storici arabi ancora più tardi riferiscono che a capo dei funzionari africani vi fosse un certo Hubahiba o Jananah, che secondo alcuni studiosi si chiamerebbe Gennadio e sarebbe l’esarca d’Africa. Le fonti islamiche riferiscono che Jananah fu detronizzato da una rivolta che lo sostituì con quello che le fonti islamiche chiamano Al-At’riyun, nome corrotto probabilmente da emendare in Eleuterio. Jananah si rifugiò presso la corte del califfo Muawiyah, chiedendogli aiuti militari per recuperare Cartagine. Nel 665 il governatore d’Egitto condusse una nuova invasione dell’Esarcato d’Africa, principalmente per fare bottino ma anche con il pretesto di aiutare Jananah a riconquistare Cartagine. Tuttavia Jananah morì ad Alessandria nello stesso anno. Inoltre, mentre la spedizione era ancora in corso, un esercito imperiale sotto il comando del patrizio Niceforo sbarcò a Hadrumetum, non è chiaro se per sconfiggere gli invasori arabi o per reprimere una rivolta della popolazione provinciale. In ogni caso l’esercito imperiale fuggì salpando all’appropinquarsi di un esercito islamico senza nemmeno affrontarlo. Gli Arabi fecero ritorno in Egitto con molto bottino nello stesso anno. Lo studioso moderno Kaegi ha messo in dubbio quanto narrato le fonti islamiche, sostenendo che durante la trasmissione della tradizione avvennero delle corruzioni che trasformarono una pluralità di funzionari bizantini in una specifica persona dal nome di “Hubahiba” o “Jananah”. Secondo Kaegi non sarebbe da escludere che la fuga di Jananah presso gli Arabi potrebbe essere stata inventata ispirandosi alla richiesta di aiuto agli Arabi di Elpidio, il governatore bizantino della Sicilia, che fornì agli Arabi il pretesto per cominciare la conquista islamica della Sicilia.
Nel frattempo il califfo Muawiyah aveva deciso di conquistare l’esarcato d’Africa. Nel 669 gli Arabi, con l’appoggio delle tribù berbere della Tripolitamia, invasero di nuovo l’Esarcato avanzando fino all’odierna Kairowan, che fu costruita dagli Arabi stessi tra il 670 e il 675 e divenne la nuova capitale della provincia islamica di Africa. Una nuova invasione dell’Africa ebbe luogo nel 683 ma gli Arabi, dopo alcuni successi iniziali, subirono nell’agosto del 683 una sconfitta contro i Mauri e gli Imperiali nella quale cadde finanche il governatore arabo. La capitale Kairowan fu evacuata dagli Arabi e occupata dai Mauri. Gli Arabi furono impossibilitati a reagire per il momento a causa di una nuova guerra civile scoppiata nel califfato, ma gli Imperiali non riuscirono ad approfittarne. L’esarcato d’Africa, che comprendeva ancora Proconsolare, parti della Numidia e una serie di città sulla costa fino a Septem, era ormai in declino.
Già tra il 686 e il 688 gli Arabi invasero di nuovo l’Africa vendicandosi della recente disfatta con una vittoria sui Mauri e con la riconquista di Kairowan. Nel 697 una nuova invasione degli Arabi riuscì addirittura a conquistare Cartagine. Secondo le fonti bizantine, nello stesso anno gli imperiali riuscirono a riconquistare Cartagine, che tuttavia cadde di nuovo in mano islamica nel 698. La popolazione di Cartagine fuggì in Sicilia, Spagna e nelle isole del Mediterraneo occidentale. E’ possibile tuttavia che all’epoca la capitale dell’esarcato fosse stata trasferita a Cagliari in Sardegna o a Septem in Mauritania Tingitana, in quanto una lettera di Giustiniano indirizzata a Papa Conone e datata febbraio 687 attesta che le armate d’Africa e di Sardegna avevano sede rispettivamente a Septem e a Cagliari. Inoltre la zecca di Cartagine era già stata spostata in Sardegna.
Agli inizi del VIII secolo i territori dell’esarcato d’Africa ancora in mano imperiale si erano ridotti a Sardegna, Corsica, Baleari e la città di Septem, l’unica città ancora imperiale dell’Africa. Nel 706 gli Arabi tentarono di espugnare Septem ma la guarnigione imperiale condotta da Giuliano respinse l’assalto. Septem cadde in mani islamiche solo nel 711.