Захват арабами Северной Африки начал эмир Египта Ибн-Сауд в 647 г., одержав в конце концов победу над войсками византийского наместника Григория. Однако византийские крепости, возведенные еще при Юстиниане, не сдались неприятелю, а берберы, позабыв о своей давней враждебности по отношению к римлянам, плечом к плечу вместе с ними вступили в борьбу с захватчиками. Вновь подтвердилось стратегическое значение Северной Африки; ведь именно после захвата расположенных здесь римских провинций вандалами начался упадок Западной Римской империи, которая отныне думала уже только об обороне. От позиций империи в Африке зависела безопасность Сицилии и Италии, а также морских путей на Запад. Безусловно, именно стремясь защитить византийские позиции в Африке, император Констанций II после своего визита в Рим — последнего визита туда императора Византии — расположился вместе со своими силами в Сиракузах.
На какое-то время из-за внутренних неурядиц и борьбы за власть в халифате Византия получила передышку. Но в 660 г., когда халифом стал Муавия, борьба вспыхнула с новой силой. В 664 г. мусульманская конница нанесла очередное поражение Византии. Византийские войска, направленные в Хадрамаут, потерпели поражение, а крепость Джелула была захвачена арабами, после чего захватчики отступили. Но для того чтобы отразить возможные атаки со стороны Византии, которая продолжала контролировать ряд городов, расположенных на побережье, а также в целях сдерживания берберов, осуществлявших вылазки с Атласских гор, Окба-бен-Нафи основал в 670 г. город Кайруан (в нынешнем Тунисе) — он должен был стать опорным пунктом мусульман на все времена. Именно Кайруан стал плацдармом распространения влияния арабов-магометан; именно отсюда предпринимались кровавые походы против берберов, по-прежнему оказывавших сопротивление арабам со своих опорных пунктов в Атласских горах. В 681 г. Окба совершил впечатляющий бросок и достиг берегов Атлантического океана. Однако в результате контрнаступления византийцев и берберов арабы были отброшены назад; берберский князь Коссайла вступил в Кайруан как завоеватель, а те берберы, которые приняли ислам, поспешили отречься от него[169]
.Теперь была очередь Византии нанести удар. Мусульмане, разбитые под Кайруаном, отступили в Барку, где были окончательно уничтожены в результате неожиданного удара византийских войск, которые высадились здесь в 689 г. Их лидер был убит в бою.
Эта победа вернула североафриканское побережье под контроль Византии и поставила под угрозу все арабские завоевания в Средиземноморье. Арабы предприняли отчаянную попытку переломить ситуацию в свою пользу и в 695 г. взяли штурмом Карфаген. Император Леонтий, осознавая всю опасность происходящего, направил туда флот под командованием патриция Иоанна, и византийцы вернули себе контроль над городом.
В это время берберы, объединившись вокруг своей таинственной королевы, известной под именем Кахина, нанесли поражение арабским войскам под Тебессой и отбросили их в Триполитанию.
Но на следующий год арабы во главе с Хасаном вновь перешли в наступление и в 689 г. захватили Карфаген, на этот раз окончательно. Жители покинули город. Функции столицы сразу же перешли от этого древнего города к Тунису, расположенному на самом севере африканского побережья, на берегу Сицилийского пролива; а гавань Туниса — Голетта — стала мощнейшей базой арабов-магометан и плацдармом распространения ислама в Средиземноморье. Арабы, у которых наконец появился флот, рассеяли византийские корабли. С тех пор контроль на море перешел к халифату. Вскоре византийцы сохраняли контроль лишь над крепостью Септем (Сеута) на побережье Гибралтара и небольшими участками территории бывшей римской североафриканской провинции Мавритания, а также над островом Мальорка и несколькими городами в Испании. Из всех этих территорий византийцы, судя по всему, сформировали отдельную административную область (экзархат), просуществовавшую еще 10 лет.
Эти события означали конец сопротивления берберов под руководством королевы Кахины. Она была взята арабами в плен в Атласских горах и убита, а ее голову отослали халифу.
В последующие годы арабы установили контроль над всей Северной Африкой. Муса ибн-Нусайр подчинил Марокко и насадил ислам среди местных берберских племен.