Все, что писали арабские историки о нападениях на берберские племена в 660–663 годах, нуждается в проверке. В 665 году бывший глава омейядской партии в Египте Муавия ибн Ходайдж вступил по приказу халифа в Бизацену, разбил византийскую армию, высадившуюся в Гадрумете, взял приступом и разграбил крепость Джалула, а затем, нагруженный добычей, вернулся в Египет.
Постоянная оккупация. Окба. Спустя некоторое время Окба ибн Нафи, который уже совершил блистательный набег на Феззан, организовал третью экспедицию, которая отличалась от двух предыдущих тем, что привела к постоянной оккупации страны. На обширной полупустынной равнине в сердце Бизацены он основал в 670 году город Кайруан. Первоначально Окба ибн Нафи якобы очистил местность от диких зверей и пресмыкающихся. По словам историка ан-Нувейри, он говорил: «Я построю город, который будет служить оплотом (Кайруан) ислама до скончания веков».
Оплот, конечно, против византийцев, которые могли использовать прибрежные города для наступления, но главным образом против берберов, которые отныне становились единственным грозным противником. Таким образом, Кайруан не только защищал путь в Египет, который должен был оставаться свободным для снабжения армии и возможного отступления, но противостоял Оресу, ставшему центром сопротивления.
Несмотря на это приобретение, Ифрикия не стала автономной провинцией, а управлялась из Египта. Окба был даже смещен без каких-либо церемоний и заменен Абу-ль-Мухаджиром, клиентом нового наместника. Возможно, что основателя Кайруана упрекали за его чисто военные концепции, за высокомерие в отношении берберских вождей, систематическую резню и столь же опасные, сколь и бесполезные набеги. В противоположность своему предшественнику Абу-ль-Мухаджир начал, кажется, переговоры с вождями племен, чтобы заручиться их поддержкой в борьбе против Византии.
Говорят также, что он дошел до «источников Тлемсена», где разбил и взял в плен могущественного и хитрого Косейлу, владыку племени ауреба. В конечном итоге политика Абу-ль-Мухаджира, менее блестящая, чем политика Окбы, была, очевидно, более плодотворной.
Поход Окбы на запад. Немилость, в которую впал Окба, длилась недолго. В 681 году он получил верховное командование в Африке и тотчас же предпринял поход в Магриб; но за достоверность этих данных ручаться было бы крайне неосторожно.
Чтобы утолить чувство мести, он вел за собой Абу-ль-Мухаджира и Косейлу, закованных в цепи, осыпая берберского вождя оскорблениями, за которые позже жестоко поплатился. Он не пытался осаждать укрепленные города на север от Ореса и, столкнувшись с туземными войсками, поддерживаемыми греческими подразделениями— румийцами — у Багаи и Ламбеза, а затем у Тиарета, пошел прямо на Танжер.
Арабские историки рассказывают, что патриций Юлиан (Илиан), отнюдь не склонный сражаться с ним, встретил его с богатыми подарками. Окба расспрашивал Юлиана о вестготах Испании, румийцах и берберах Магриба. По его указаниям он проник в Сус, где учинил резню и устроил охоту на девушек, призывая бога в свидетели того, что только Атлантический океан помешал ему идти дальше и истреблять неверных.
Все это очень любопытно, и Э.-Ф. Готье даже построил на этом теорию: он считает, что можно провести параллель между легко удавшейся оккупацией Тингитаны и оккупацией Ифрикии, а позднее и Испании. По его мнению, все земли Северной Африки, испытавшие на себе карфагенское влияние, легко примыкали к мусульманам. Однако большинство деталей появляется только у позднейших историков: у Ибн Абд аль-Хакама, да и то еще не во всех преданиях, которые он приводит, находят только упоминание о Сусе (термин весьма неопределенный у позднейших арабских географов, значение которого в VIII веке следовало бы уточнить) и о знаменитом слове Окбы, который остановился на берегу моря (неизвестно какого) и призвал в свидетели бога, что он не может идти дальше. Нет никаких упоминаний о Танжере, никаких подробностей об этом беспримерном набеге на неизвестную страну. Здесь есть о чем задуматься и в чем усомниться. Окба стремился распространить мусульманское владычество на запад и с этой целью вел войну в Оресе. Однако было бы слишком смело утверждать нечто большее. «Если можно рассматривать поход Окбы как действительно имевший место, было бы благоразумно в ожидании доказательств противного ограничить этот поход центральным Алжиром; он, возможно, достиг самое большее нынешней Орании и долины Шелифа» (Р. Бруншвиг).