В 758 году в Андалусию переправился Абд ар-Рахман Пришелец, один из последних представителей династии Омайядов, свергнутых в 750 году Аббасидами. Абд ар-Рахман, прозванный аббасидским халифом аль-Мансуром «соколом курайшитов» (племени, из которого происходил пророк Мухаммад, Омайяды и Аббасиды), установил в Андалусии власть Омайядов, приняв титул эмира.

Постепенно Андалусия приобретала все большее влияние на юге Европы, ведя почти всегда успешные войны со своими северными соседями — королями и князьями, правителями Наварры, Леона, Арагона, Кастилии, Басконии, отражая нападение «маджус» — «магов» или «северных язычников» — норманнских пиратов, которые в то время опустошали берега Европы. Армия и флот Андалусии считались одними из лучших в Европе. Но подлинного спокойствия в Андалусии не было. То тут, то там прорывалось недовольство коренных жителей Андалусии, принявших ислам, так называемых мувалладов. Иногда муваллады даже обращались за помощью к христианским правителям Европы. Так, в 828 году муваллады города Мериды обратились к королю Франции Людовику Благочестивому (814—840), который ответил им следующим посланием: «Мы услышали рассказ о страданиях, которые вы терпите из-за жестокости вашего короля… Он превратил вас во врагов, хотя до этого вы были его друзьями, из верных подданных он сделал вас мятежниками… и так как он не только ваш, но и наш враг, будем вместе сражаться против его притеснений…»

Может быть, ободренные обещанием короля, которое так и не было выполнено, муваллады попытались свергнуть власть арабов, В конце IX — начале X века почти весь юго-запад Андалусии был захвачен мувалладами, вождем которых был Ибн Хафсун. Омайядскому эмиру Мухаммаду лишь в течение нескольких лет и с большим трудом удалось подавить это восстание.