Более успешно арабы действовали в Северной Африке. Центром африканских владений Византии был Карфаген. Сюда бежали из Египта многие христиане, среди них было немало монофизитов, спасавшихся от преследований византийской администрации и ортодоксальной православной церкви. Неурядицы в Константинополе, где после смерти императора Ираклия кипела борьба за власть, способствовали стремлениям части местной знати отделиться от империи. Так, например, в 645 г. правитель Северной Африки экзарх Григорий провозгласил себя императором.

В 667 г. в Северную Африку направился 10-тысячный отряд под командованием Укбы ибн Нафи. Захватив часть византийских владений, Укба основал город Кайруан, ставший опорным пунктом дальнейших завоеваний. В 683 г. войска Укбы продвинулись до Мавритании. По преданию, Укба дошел до Атлантического океана и въехал на коне в его воды. Конь зафыркал и попятился. Тогда Укба воскликнул: «Аллах! Зову тебя в свидетели, что далее идти нельзя!». На самом деле арабы вышли к океану лишь через 20 лет, а Укба вскоре попал в засаду и погиб.

Арабам пришлось действовать не только против византийского войска, но и преодолевать сопротивление берберов, коренного населения Северной Африки. К началу VIII в. Карфаген пал, в руках арабов оказалась вся полоса североафриканского побережья от Египта до Атлантического океана. Берберские племена подчинились завоевателям и приняли ислам.

Арабское завоевание привело к разорению одной из богатейших провинций Византийской империи. По словам арабского историка, «большинство городов Ифрикии (арабское название Африки. – Т. С.) опустошены вследствие сопротивления, оказанного берберами, селения покинуты жителями, хозяйственные заведения сожжены, оросительные работы запущены».