Окба скоро был отозван из Африки, и на его место назначен Абу-Могаджир. Но это не имело существенного значения для экзархата, т. к. разжалованный генерал снова вошел в милость калифа и получил в управление Африку. В 683 г., оставив в Кайруане небольшой гарнизон, он бросился на запад, чтобы докончить подчинение византийской Африки, и, не приняв никаких мер к защите отступления на случай возможной неудачи, неосторожно дошел до Мавритании, хотя в тылу у него составился значительный отряд из берберов и остатков византийских гарнизонов, имевший целью отрезать ему отступление. Действительно, когда Окба считал кампанию оконченной, дошедши, по арабским, преувеличенным конечно, известиям, до берегов Атлантического океана или до нынешнего Танжера, на возвратном пути к Кайруану он был окружен восставшими племенами в своей стоянке близ Тегуды, где пал геройской смертью. Ближайшим следствием этого поражения было то, что опорный пункт арабов в Кайруане был утрачен, и еще на десять лет продолжено было в Африке господство императора.
Наступательное движение против византийских приморских владений в Африке вновь обнаруживается в 693 г., когда калиф Абд ель-Мелик отдал распоряжение о начатии действий против Карфагена. Наместником калифа в Африке был Гассан ибн Номан, занятый в то время подготовлением средств для борьбы с обширным союзом берберийских племен, стоявшим под управлением храброй царицы, известной под именем Кагены, или Волшебницы, которая имела среди воинственных горных племен громадный авторитет. Мусульманский вождь открыл кампанию смелым и решительным движением против главных позиций, остававшихся во власти Византии на морском берегу, и в 695 г. осадил столицу экзархата Карфаген. После битвы под стенами города, в которой экзарх потерпел поражение, Карфаген взят приступом и занят мусульманами. Остатки войска и часть романизованного населения искали спасения в Сицилии и на островах; большинство же населения взято в плен и обращено в рабство. Но это не был еще заключительный акт истории Африканского экзархата под византийской властью.