Экспедиция в СевероЗападную Африку; основание Кайруана

Когда Амр ибн альАс был заново назначен Муавией наместником Египта в 658 г., его племянник Укба ибн Нафи, энергичный и импульсивный воин, начал кампанию в контролируемый Византией регион Северной Африки, к западу от Египта (666 г.). Так как его военной базой первоначально являлся Фустат, а атаки производились на расстояние больше 2 тысяч километров, это создавало опасность для тыла и перебои с провиантом. Для преодоления этого недостатка, в 670 г. Укба заложил военный лагерь в Кайруане (совр. Тунисская Республика), и основал правительство провинции со столицей здесь. Новый гарнизон, подобно Басре, Куфе и Фустату перед этим, позднее превратился в знаменитый город, с Великой мечетью. Эта мечеть стала важным интеллектуальным центром, а сам город — отправной точкой расширения территорий в Северной Африке в период Омейядов.

Горные области Атласа, к северу от пустыни Сахара, издревле были населены берберами — народом семитского происхождения, всегда оказывавшим упорное сопротивление. Мусульмане столкнулись в этом ареале с двумя силами с двух разных направлений — берберами с гор Атласа, и византийцами с их крепостей с морского побережья. Хотя Кайруан лежал в нескольких километрах от побережья и, таким образом, был в безопасности от атак со Средиземноморья, он был расположен слишком близко к территории берберов. В прошлом, византийцы сохраняли контроль над регионом из их местной провинциальной столицы, античного города Карфагена (впервые основан в сер. IX в. до Р. Х. финикийцами, расположен в 16 километрах к северовостоку от совр. Туниса) на побережье.

Cоюз с берберами заключен не был. Вместо этого Укба был атакован с двух сторон одновременно, виной чему послужило надменное обращение с горцами. По возвращении из этого опасного путешествия на запад, он был убит из засады в 683 г. около современного города Бискра в Алжире. Вскоре после его гибели берберы подняли восстание, и почти все территории были утрачены, включая и Кайруан; западной границей управляемого Амром Египта и всего мусульманского мира вновь стала Киренаика (известная как Барка; в совр. Ливии). Тем не менее почва была подготовлена, что дало свои плоды в будущем.