В этот же период арабы несколько раз предпринимали решительные наступления на византийцев. В начале своего правления, еще когда Ибн аз-Зубайр боролся за власть, Абдул-Малик уплатил дань (70 г. хиджры, 689–690 г. н. э.) «тирану римлян», а также его христианским союзникам джураджима, к тому времени обосновавшимся в Ливане. Но вскоре после этого Абдул-Малик смог собраться с силами и перейти в атаку на исконного врага. В 692 году его войска разбили войска Юстиниана II в киликийском Севастополе. Преемник Абдул-Малика аль-Валид продолжил наступление. Около 707 года его войска заняли Тиану (Ат-Тавана), самую сильную крепость Каппадокии. После захвата Сардиса и Пергама открылся путь в Константинополь. Брат и военачальник Сулеймана Маслама взял город в осаду. Это было памятное, но напрасное мероприятие, продлившееся с августа 716 года по сентябрь 717-го. Армения, захваченная (644–654) еще когда Муавия был наместником в Сирии, воспользовалась разгромом Ибн аз-Зубайра, чтобы восстать, но снова была укрощена при Абдул-Малике.

В это же самое время пришлось отвоевывать и Ифрикию. Военачальник Муавии Укба оказался в настолько непрочном положении в этом регионе, что его преемнику пришлось вывести оттуда войска. При Абдул-Малике Хасан ибн ан-Нуман аль-Гассани (693–700) положил конец сопротивлению берберов и византийскому влиянию. С помощью мусульманского флота он изгнал византийцев из Карфагена (698) и других городов на побережье. Затем он преследовал и разгромил их союзницу, предводительницу берберов, пророчицу (араб. кахина), которая управляла своими подданными каким-то мистическим образом. Эту легендарную героиню убили в горах Орес (Аврас), Алжир, возле источника, который до сих пор носит ее имя – Бир аль-Кахина.

За Хасаном последовал знаменитый Муса ибн Нусайр. При нем Ифрикия, управлявшаяся из Кайруана, административно отделилась от Египта и перешла под прямое правление халифа в Дамаске. Муса родился в окрестностях Бейрута. Его отец был из пленных сирийцев-христиан, который попал в руки Халида ибн аль-Валида вместе с другими мальчиками, когда они изучали Евангелия в церкви Айн-Тамра в Ираке. Именно Муса расширил границы провинции на запад до Танжера (Танджа).

Завоевания Хасана и Мусы навсегда вернули берберов в лоно ислама. Большинство берберов, проживавших тогда на плодородной земле на краю моря, были христианами. Из их среды выделились такие святые и князья раннехристианской церкви, как Тертуллиан, Киприан, Августин и другие. Византийские поселения, как и римские до них, ограничивались приморскими городами. Они были представителями культуры, которая по-прежнему оставалась чуждой кочевым и полукочевым племенам Северной Африки. Берберы испытывали куда большую склонность к арабам-мусульманам. Будучи хамитами, они стояли ближе к семитам. В то время и те и другие находились на одном уровне культуры. Более того, по-видимому, их общение облегчал факт завоевания и колонизации этого региона древними финикийцами. По арабским преданиям, большинство берберов происходит от ханаанеев. Незадолго до мусульманского завоевания местные жители в труднодоступных местах все еще говорили на пуническом языке, который, как и арабский, относится к семитским. Это объясняет, казалось бы, необъяснимое чудо – столь молниеносный и полный переход берберов в лоно ислама и арабской культуры. Как только арабы одолели берберов, они сразу же включили их в качестве очередного опорного пункта в продолжающемся поступательном движении ислама.