W 695 roku na kolejny podbój wyruszyła z Cyrenajki wielka armia arabska pod wodzą Hasana ibn Nomana al Ghasaniego i odniosła spektakularny sukces: Kartagina zdobyta, mieszkańcy wymordowani lub wzięci w niewolę, tylko niektórym udało się schronić na Sycylii albo w Hiszpanii.
Dwa lata później z Konstantynopola wypływa spora flota, by odbić miasto. Równocześnie w górach wybucha powstanie Berberów Dżerawa, tym razem pod wodzą wyznającej judaizm władczyni i prorokini Al Kahiny. Arabowie znów się wycofują do Cyrenajki, a wojownicy żydowskiej królowej obracają wszystko w perzynę, by zniechęcić Arabów do kontynuowania podboju. Miejscowi, zromanizowani rolnicy mają tego dość. Wypatrują z utęsknieniem Arabów, a gdy ci się pojawiają, szybko się im poddają. W 698 roku wyludniona Kartagina zostaje ponownie zdobyta, ostatnie punkty bizantyjskiego oporu złamane, a straszna Kahina – pokonana i zabita.
Od tej pory Berberowie do lat 30. VIII wieku, jak wszyscy niewierni, musieli płacić podatek gruntowy (charadż) i pogłówne (dżizja), które od czasu namiestnika Musy ibn Nusajra polegało na zabieraniu kontyngentu (kwinty) niewolników obojga płci. Efekt – wyludnienie miast i nizin, ucieczka ludności w góry.
Berberów traktowano jak niewiernych, ale nie pogan, tylko „ludzi Księgi”. Czy byli nimi? Częściowo tak. Pamiętamy, że Kosejla był chrześcijaninem. Ekspansję chrześcijaństwa na tych terenach znacznie ułatwiła obecność gmin żydowskich w rzymskiej Afryce. Głoszenie Ewangelii zaczynało się zazwyczaj od miejscowej synagogi. Rolę Żydów w chrystianizacji doceniali afrykańscy Ojcowie Kościoła. Tertulian zalecał np. katechetom brać pod uwagę zastrzeżenia rabinów przy objaśnianiu wydarzeń Starego Testamentu, a św. Augustyn zwracał się do rabinów o pomoc w wyjaśnianiu niezrozumiałych słów hebrajskich.
Nieprzypadkowo na starożytnym cmentarzu żydowskim w Gamart odkryto także groby chrześcijańskie. Chrześcijaństwo zapuściło tu z czasem bardzo mocno korzenie, których przyniesiony przez arabskich zdobywców islam długo nie był w stanie wyrwać. W oazach na południu Tunezji skupiska chrześcijan można było spotkać jeszcze w XV wieku. Struktury kościelne przetrwały tu do połowy XI wieku. W VIII stuleciu w Afryce Północnej istniało aż 30 biskupstw i arcybiksupstwo Kartaginy, podporządkowanych patriarchatowi aleksandryjskiemu.