Что не может не поражать историка, это полное отсутствие данных для суждения о том, как отнеслись византийцы к постройке Кайруана и предпринимали ли какие попытки, чтобы выбить арабов из занятой ими позиции. «Основание Кайруана, — говорит Диль, — имело неисчислимые последствия для будущих судеб Африки. Прежде, когда мусульманские экспедиции направлялись из Египта или из Барки, соединенные с ними опустошения при всей их беспощадности были всегда ограничены по времени, и между византийскими владениями и арабами образовали заслон берберийские племена Триполи и Бизация, которые до известной степени ослабляли напор врагов. Теперь, на границах самой Проконсульской провинции возвышалась цитадель, занятая сильным гарнизоном, откуда будут беспрестанные вылазки против крепостей, защищающих пограничную область (limes), постоянные опустошения, нарушающие покой провинции. Каждая новая экспедиция здесь найдет безопасное место для склада добычи; здесь в случае неудачи она имеет возможность запастись свежими силами. И, между тем как византийская провинция под этим постоянным напором будет постепенно приближаться к погибели, мусульманство победоносно будет расширяться из Кайруана по всей Африке, и религиозная пропаганда, идя рядом с завоеваниями, укрепит эти последние. Конечно, еще около 30 лет византийцы будут с мужеством и по временам с успехом вести борьбу; тем не менее, основание Кайруана обозначает решительный поворот к падению Африканского экзархата» 10.
Окба скоро был отозван из Африки, и на его место назначен Абу-Могаджир. Но это не имело существенного значения для экзархата, т. к. разжалованный генерал снова вошел в милость калифа и получил в управление Африку. В 683 г., оставив в Кайруане небольшой гарнизон, он бросился на запад, чтобы докончить подчинение византийской Африки, и, не приняв никаких мер к защите отступления на случай возможной неудачи, неосторожно дошел до Мавритании, хотя в тылу у него составился значительный отряд из берберов и остатков византийских гарнизонов, имевший целью отрезать ему отступление. Действительно, когда Окба считал кампанию оконченной, дошедши, по арабским, преувеличенным конечно, известиям, до берегов Атлантического океана или до нынешнего Танжера, на возвратном пути к Кайруану он был окружен восставшими племенами в своей стоянке близ Тегуды, где пал геройской смертью. Ближайшим следствием этого поражения было то, что опорный пункт арабов в Кайруане был утрачен, и еще на десять лет продолжено было в Африке господство императора.
Наступательное движение против византийских приморских владений в Африке вновь обнаруживается в 693 г., когда калиф Абд ель-Мелик отдал распоряжение о начатии действий против Карфагена. Наместником калифа в Африке был Гассан ибн Номан, занятый в то время подготовлением средств для борьбы с обширным союзом берберийских племен, стоявшим под управлением храброй царицы, известной под именем Кагены, или Волшебницы, которая имела среди воинственных горных племен громадный авторитет. Мусульманский вождь открыл кампанию смелым и решительным движением против главных позиций, остававшихся во власти Византии на морском берегу, в 695 г. осадил столицу экзархата Карфаген. После битвы под стенали города, в которой экзарх потерпел поражение, Карфаген взят приступом и занят мусульманами. Остатки войска и часть романизованного населения искали спасения в Сицилии и на островах; большинство же населения взято в плен и обращено в рабство. Но это не был еще заключительный акт истории Африканского экзархата под византийской властью.
Гассан, оставив гарнизон в Карфагене, поспешил против царицы Кагены, которая, спустившись с горных вершин Нумидии, расположилась лагерем в долине Багайя. Около царицы собрались не только берберийские племена, но и значительная часть местного культурного и христианского населения-все те, для кого нежелательно было усиление мусульманской власти. Произошла битва на берегах речки Уэд-Нини, в которой арабам нанесено было страшное поражение. Вот почему грекам снова могло улыбнуться счастье в Африке. В то время, как Гассан испытал поражение от союза берберийских племен и, не имея средств держаться в завоеванной стране, отступил в Пентаполь, к Карфагену прибыл греческий флот под предводительством патрикия Иоанна и без труда овладел городом, восстановив в приморских частях экзархата византийскую власть (697). Но это продолжалось один лишь год, потому что в 698 г. греческий флот должен был отступить из Карфагена под угрозой мусульманских морских судов.