После гражданской войны арабы продолжили завоевания в Северной Африке. В 665 году началось новое военное вторжение в Африканский экзархат. В 689 году новая североафриканская военная кампания была закончена. Армия византийских греков (30 000 солдат) была побеждена в процессе этой кампании. К 40 000 мусульман, начавших эту войну, вскоре прибыли ещё 10 000 арабов во главе с арабским генералом Укбой ибн Нафи. Выйдя из Дамаска, армия прошла почти всю Северную Африку. В 670 году захваченный арабами город Кайруан был перестроен, стал сильной крепостью и основой для дальнейших военных действий. Этот город стал столицей Исламской области Ифрикии (арабское название Туниса). Город-крепость прикрывал прибрежные районы того, что является сегодня Западной Ливией, Тунисом, и Восточным Алжиром. После обустройства Кайруана арабы снова продолжили завоевание Магриба (так называли арабы северо-западную Африку). В процессе завоевания Магриба Укба ибн Нафи захватил прибрежный город Буджия и современный город Танжер. Оба города когда-то входили в состав римской Мавретании.
Но Укба не смог долго удерживать завоеванные земли. В тылу его армии вспыхнуло восстание берберов. Вскоре его отозвали назад вместе с его войском на подавление этого восстания. В одном из сражений против греко-африканских мятежников Укба ибн Нафи погиб. На его место пришёл новый полководец Зухейр, но он также погиб в борьбе с мятежниками. Константинополь к тому времени уже успел послать в Африку большое войско.
Тем временем новая гражданская война вспыхнула в Аравии и Сирии. Завоевательные походы арабов снова были приостановлены.
Третье вторжение Арабы смогли вернуть под контроль утраченные страны Закавказья. В 687 году арабы взяли Картли, Кахети и Эрети — три княжества Восточной Грузии, но Кахети и Эрети находились на выгодном местоположении, поэтому арабы не смогли закрепиться там. 10 лет спустя, в 697 году арабы двинулись уже на запад Грузии. Наместник Эгриси — крупнейшего в Западной Грузии государства, зависимого от Византии — пригласил арабов занять гарнизоны и изгнать греков. Однако в Западной Грузии относительно надолго арабы закрепились лишь в Эгриси (это обуславливалось родным тропическим для завоевателей климатом и сильными гарнизонами и крепостями, а также центральным положением страны в Западной Грузии): Абасгия и Апсилия (кроме южной, принадлежавшей Эгриси) освободились уже в 711 году. Чанети, на которую арабы тоже посягали, осталась в сфере влияния Византии. Но так или иначе, к 700 году арабы захватили все Закавказье за исключением горной Мисиминии и Алании, которая была на стороне византийско — хазарского альянса. Новое завоевание Северной Африки началось с повторного взятия арабами городов Ифрикии. Но Византия быстро перебросила войска из Константинополя. К византийцам присоединились солдаты из Сицилии и сильный контингент вестготов из римской Испании. Это вынудило арабскую армию отступить к Кайруану. Следующей весной арабы предприняли новые наступления морским и сухопутным путём. Вскоре они разбили византийцев и их союзников в битве при Карфагене. В 698 году арабы вошли в Карфаген. Его камни послужили материалом для строительства города Туниса. Другой бой велся около Утики, и арабы снова победили, вынудив византийцев оставить Северную Африку. Пять лет прошли, прежде чем Хасан ибн аль-Нуман, новый генерал мусульман, получил новые войска из Халифата. Тем временем люди, в ещё не захваченных городах Северной Африки, стали гневаться на берберское господство. Таким образом, Хасана приветствовали по его возвращении. В 709 году арабы захватили почти всю Северную Африку и поделили её на три области: Египет с его губернатором в аль-Фустате, Магриб (современные Марокко и Мавритания) с губернатором в Фесе и Ифрикия с её губернатором Мусой ибн Нусайром. Муса ибн Нусайр был генералом. Он был назначен губернатором Ифрикии и нёс ответственность за подавление возобновленного берберского восстания и распространения ислама в завоеванных землях. Муса и его два сына имели 300 000 пленников. Почти все пленники были проданы в рабство и доходы от их продажи поступили в общественное казначейство. Ещё 30 000 пленников были принуждены нести военную службу. Mуса также имел дело с постоянными набегами византийского флота. Для борьбы с ним Муса построил собственный флот. Продвигаясь вглубь Магриба, его силы взяли Танжер в 709 году.