И тем более можно пожалеть о горячности, с которой обсуждались церковные споры, что Констант II сознавал всю важность переживаемых событий и с целью противодействия арабам и удержания западных областей в связи с империей решился на экстренные средства, перенеся на некоторое время свое пребывание в Сицилию и приняв меры к укреплению Карфагена и к усилению средств защиты в Африке. К сожалению, все это требовало новых материальных средств и вызвало увеличение повинностей, которые ложились тяжелым бременем на Африканский экзархат и усилили раздражение против власти императора. Когда в 665 г. арабы готовили большую экспедицию в Африку, эта страна находилась в полном брожении: экзарх был изгнан из Карфагена и заменен самовольно избранным начальником, туземные берберийские племена находились в анархии и готовы были охотней подчиниться мусульманам, чем сносить тяжелую зависимость от императора. Прочные завоевания в Африке начались после 665 г., когда арабское войско вторглось в византийскую область и начало опустошать во всех направлениях Бизацену. Император послал из Сицилии отряд в 30 тыс. под предводительством патрикия Никифора, который, однако, не остановил арабов, но потерпел от них поражение. Богатая добыча, взятая арабами в этом походе, и легкость, с которою удалось им выгнать греков даже из некоторых укрепленных мест, внушили им уверенность, что византийская Африка может быть ими занята без особенных трудностей.
Исполнителем воли калифа на этот раз явился Окба ибн Нафи, который с 10-тысячным отрядом проник в византийскую область. Для ясности изложения следует сказать, что провинция Африка, или арабский термин «Ифрикия», обнимала главным образом приморские области, начиная от Египта: частью Пентаполь с городом Барка, далее провинцию Триполь, затем Бизацену, Нумидию, Африку с Карфагеном и Мавританию, или Магриб. Пентаполь и Триполь были присоединены к арабским владениям вслед за подчинением Египта; следовательно, к экзархату Африки в занимающее нас время относились области, начиная с Бизацены. Таким образом, все географические термины, которые далее встретятся в изложении арабских походов, относятся к пограничным местам между Триполи и Бизаценой. Во время похода Окбы ибн Нафи в 667–668 гг. провинция Триполь до острова Джербы перешла уже под власть арабов, равно как и внутренняя полоса земли с оазисами Уаддан и Феццан. Это была эпоха наибольшего потрясения империи: насильственная смерть царя Константа II в Сиракузах и появление двух бунтовщиков, объявивших себя императорами в Сицилии и в Малой Азии, побудили Константина Погоната собрать все силы, какими располагала империя, для борьбы с самозванцами. Это дало возможность арабам не только без помехи распорядиться с приобретенными областями, но и обеспечить на будущее время обладание значительной частью экзархата.
С этой целью Моавия приказал Окбе утвердиться в завоеванной области и основать на границах Бизацены укрепленный лагерь. Арабский полководец увеличил свой отряд свежими силами из берберов, завоевал новые области на юг от Триполи и двинулся далее на северо-запад к Бизацене, заняв Кастилию и Гафсу. Но самым смелым и важным в стратегическом отношении было то, что он пришел к мысли основать город Кайруан (670) поблизости от морского берега, избрав его опорным местом для господства в Африке и для будущих военных предприятий против империи. Этот город возник на обширной болотистой равнине, в небольшом расстоянии от Гадрумета и при подошве гор, которые защищали византийскую область. Не обращая внимания на неблагоприятные условия почвы и на возражения военных людей, он в течение пяти лет с настойчивостью занимался устройством города и приготовил в нем опорный пункт для новых завоеваний и убежище на случай поражения. Впоследствии здесь образовался прекрасный город со множеством роскошных мечетей и частных зданий и вместе с тем важный торговый пункт.