Al-Andalus atau Semenanjung Iberia (Spanyol dan Portugal termasuk selatan Perancis sekarang) mulai ditaklukan oleh umat Islam pada zaman khalifah Bani Umayyah, Al-Walid bin 'Abdul Malik (705-715), di mana tentakel Islam sebelumnya telah menguasai Afrika Utara dan menjadikannya sebagai salah satu provinsi dari Bani Umayyah. Penguasaan sepenuhnya atas Afrika Utara ini terjadi pada masa 'Abdul Malik bin Marwan (685-705), di mana dia mengangkat Hasan bin An-Nu'man menjadi gubernur di daerah itu. Selanjutnya dalam proses penaklukan Spanyol ini terdapat tiga pahlawan Islam yang dapat dikatakan paling berjasa yaitu Tharif bin Malik, Thariq bin Ziyad, dan Musa bin Nushair. Pada masa ini, Hasan bin An-Nu'man al-Ghassani sudah digantikan oleh Musa bin Nushair, yang kemudian memperluas wilayah kekuasaannya dengan menduduki Aljazair dan Maroko. Selain itu, ia juga menyempurnakan penaklukan ke daerah-daerah bekas kekuasaan bangsa Barbar di pegunungan-pegunungan, sehingga mereka menyatakan setia dan berjanji tidak akan membuat kekacauan-kekacauan seperti yang pernah mereka lakukan sebelumnya. Sedangkan penaklukan atas wilayah Afrika Utara ini, dari pertama kali dikalahkan sampai menjadi salah satu provinsi dari Khilafah Bani Umayah memakan waktu selama 53 tahun, yaitu mulai tahun 660 (masa pemerintahan Muawiyah bin Abu Sufyan) sampai tahun 705 (masa Al-Walid I). Sebelum dikalahkan dan kemudian dikuasai Islam, di kawasan ini terdapat kantung-kantung yang menjadi basis kekuasaan kerajaan Visigoth. Kerajaan ini sering menghasut penduduk agar membuat kerusuhan dan menentang kekuasaan Bani Umayyah. Setelah kawasan ini betul-betul dapat dikuasai, umat Islam mulai memusatkan perhatiannya untuk menaklukkan Spanyol. Dengan demikian, Afrika Utara menjadi batu loncatan bagi kaum muslimin dalam penaklukan wilayah Al-Andalus.