“安达卢斯”这一地名首次出现在716年伊比利亚新穆斯林政府铸造的硬币铭文上。
这些硬币称为第纳尔（dinars），上面同时刻有拉丁文和阿拉伯文。
传统上认为，“安达卢斯”这个名字的词源来源于汪达尔人（Vandals，西班牙语为vándalos，葡萄牙语为vandalos）的名字。
---
在倭马亚（Umayyad）哈里发瓦利德一世（Al-walid I）统治期间，指挥官塔里克·伊本·齐亚德（tariq ibn-Ziyad）率领一支7000人的军队于711年4月30日登陆直布罗陀，名义上是介入西哥特人（Visigothic）内战。
在711年7月19日的瓜达莱特战役（battle of Guadalete）中，塔里克战胜了罗德里克国王（King Roderic），随后塔里克与他的隶属——北非伊弗里基亚省（Ifriqiya）总督穆萨·伊本·努赛尔（musa ibn Nusayr）一起，在为期七年的战争中将大部分西哥特王国置于穆斯林统治之下。
他们还越过比利牛斯山脉，占领了位于南法的西哥特塞普蒂马尼亚（Septimania）。
伊比利亚半岛的大部分地区成为不断扩展的倭马亚帝国（Umayyad Empire）的一部分，称为安达卢斯。
它被作为一个隶属于伊弗里基亚（Ifriqiya）的省份进行管理，因此，在最初的几十年里，安达卢斯的总督是由凯鲁万（Kairouan）的酋长任命，而不是由大马士革（damascus）的哈里发任命。
区域首府设在科尔多瓦（cordoba），首批穆斯林定居者被广泛分布在各地。
---
随着穆斯林征服西班牙，安达卢斯在其最大范围内被划分为六个行政区，大致对应现代的安达卢西亚（Andalusia）、卡斯蒂利亚和莱昂（castile and Leon）、纳瓦拉（Navarre）、阿拉贡（Aragon）和加泰罗尼亚（catalonia）、葡萄牙（portugal）和加利西亚（Galicia），以及位于奥克西塔尼亚（occitania）的朗格多克-鲁西永地区（Languedoc-Roussillon）。
塔里克最初征服时所率领的军队主要是柏柏尔人，而穆萨带领的大约1.2万士兵则主要是阿拉伯人，他们还带来了许多非阿拉伯的穆斯林“隶属”（mawāli，阿拉伯语：?????），即阿拉伯人的客户。
随塔里克征战的柏柏尔士兵驻扎在伊比利亚半岛的中部和北部地区以及庇里牛斯山脉，随后跟随而来的柏柏尔移民则定居在全国的各个部分——北部、东部、南部和西部。
那些愿意承认穆斯林宗主权的西哥特领主得以保留自己的封地（特别是在穆尔西亚、加利西亚和埃布罗河谷）。
顽抗的西哥特人则逃往坎塔布连山地（cantabrian highlands），在那里建立了残余的阿斯图里亚斯王国（Kingdom of Asturias）。
---
在720年代，安达卢斯的总督们多次向阿基坦（Aquitaine）发起劫掠性赛伊法突袭（sa'ifa raids），但在721年图卢兹战役（battle of toulouse）中被阿基坦公爵伟大的奥多（odo the Great）彻底击败。
然而，在击溃了奥多的柏柏尔盟友乌斯曼·伊本·奈萨（Uthman ibn Naissa）后，阿卜杜勒·拉赫曼·阿尔·加菲基（Abdul Rahman Al Ghafiqi）率军北越庇里牛斯山西部，击败了阿基坦公爵，奥多随后向法兰克领袖查理·马特（charles martel）求援，并愿意接受卡洛林王朝的宗主权。
在732年的图尔战役（ battle of tours \/ battle of poitiers）中，安达卢斯的突袭军被查理·马特击败，阿尔·加菲基战死。
在734年，安达卢斯军队向东发动突袭，占领了阿维尼翁（Avignon）和阿尔勒（Arles），并征服了普罗旺斯的大部分地区。
737年，他们沿罗讷河谷（Rh?ne valley）一路北上，甚至到达了勃艮第（burgundy）。
法兰克国王查理·马特在伦巴第王（Liutprand of the Lombards）的协助下入侵勃艮第和普罗旺斯，最终在739年驱逐了安达卢斯的突袭者。
740年，北非（马格里布）的柏柏尔人起义（berber Revolt）爆发。
为平息叛乱，倭马亚哈里发希沙姆（hisham）派遣了一支由比拉德·阿什-沙姆（bilad Ash-Sham）部队组成的大军前往北非。
然而，这支强大的倭马亚军队在巴格杜拉战役（battle of bagdoura，摩洛哥）中被柏柏尔叛军彻底击败。
受北非兄弟们胜利的鼓舞，安达卢斯的柏柏尔人迅速发动了自己的起义。
驻扎在伊比利亚半岛北部的柏柏尔驻军叛变，罢免了他们的阿拉伯指挥官，并组织了一支大规模的叛军，向托莱多（toledo）、科尔多瓦（cordoba）和阿尔赫西拉斯（Algeciras）等据点进军。
741年，巴尔杰·本·比什尔（balj b. bishr）率领大约1万名阿拉伯部队渡过海峡。
安达卢斯的阿拉伯总督联合这支部队，在742年的一系列激烈战斗中击败了柏柏尔叛军。
然而，叙利亚指挥官与安达卢斯的“原阿拉伯人”之间立即发生了争执。
在742年8月的阿夸波托拉战役（battle of Aqua portora）中，叙利亚军队赢得了艰难的胜利，但他们人数太少，无法对整个省份实施控制。
743年，新任安达卢斯总督阿布·哈塔尔·侯萨姆（Abu l-Kha??ār al-?usām）将叙利亚人分配到安达卢斯的各个军区封地中——
大马士革军区（damascus jund）在埃尔维拉（Elvira，格拉纳达Granada）、
约旦军区（Jordan jund）在赖尤（Rayyu，马拉加和阿尔奇多纳）、
巴勒斯坦军区（Jund Filastin）在麦地那-西多尼亚（medina-Sidonia）和赫雷斯（Jerez）、
赫姆斯军区（Emesa jund）在塞维利亚（Seville）和尼耶布拉（Niebla）、
基纳斯林军区（qinnasrin jund）在哈恩（Jaén）、
埃及军区（Egypt jund）则分散在西部的贝雅（beja，位于阿连特茹 \/ Alentejo， 今葡萄牙）和东部的图德米尔（tudmir，穆尔西亚 \/ murcia）之间。
叙利亚人的到来大大增加了伊比利亚半岛上的阿拉伯人数量，并巩固了穆斯林对南部的控制。
然而，叙利亚军区不愿被统治，他们过着自治的封建无政府状态的生活，严重削弱了安达卢斯总督的权威。