Dalsze podboje w Afryce doprowadziły muzułmanów do Ceuty, którą opanowali między 705 a 710 rokiem. Ekspansja na południowym wybrzeżu Morza Śródziemnego nie była jednak regularną, lądową kampanią. Arabowie wykorzystywali floty swoich nowych poddanych z Egiptu i z SyriiFrend W.H.C., The Rise of the Monophysite Movement, Cambridge, 1972. i stopniowo zajmowali najbardziej ludne i strategiczne regiony w północnej Afryce, takie jak Cyrenajka czy Kartagina. Ich kontrola nad tymi terenami nie była jednak pełna, często zadowalali się zajęciem najważniejszych ośrodków miejskich i zabezpieczeniem szlaków komunikacyjnych, a miejscowe społeczności czy też berberskich wodzów pozostawiano w spokojuCrone Patricia, Cook Michael, Hagarism: The Making of the Islamic World, Cambridge, 1977.. Z czasem zaczęło dochodzić do walk, zwłaszcza między Arabami i Berberami, ale ostatecznie ci drudzy dostrzegli wiele korzyści w sojuszu z muzułmanami i sami zaczęli przyjmować islam. Procesy te trwały jednak bardzo długo i postępowały stopniowo.