Мусульманское завоевание Пиренейского полуострова и Септимании (Лангедока) в 710-х годах несколько изменило положение вещей. В вестготской Испании, сотрясаемой последствиями арианского раскола и раздорами среди местной аристократии, уже нарастало беспокойство: туда дошли первые известия о продвижении арабов вдоль побережья северной Африки. На Толедском соборе 694 года король Эгика произнес речь, полную тревоги. Распространялся слух о том, что евреи, доведенные до отчаяния притеснениями, охотно оказывали помощь новым варварам, шедшим с Востока. Тем временем бушевала гражданская война между претендентами на толедский престол. Похоже, что один из них, желая любой ценой взойти на трон, обратился за помощью к mauri — арабам-завоевателям, а также к арабизированным и исламизированным берберам: к тем, которые отныне навсегда станут los moros, маврами, соседями испанцев-христиан, их свирепыми и завораживающими воображение врагами. С другой стороны, существует предположение, что в Испании и в Септимании, как прежде на многих византийских землях, завоеванных мусульманами, пришельцы были встречены населением отнюдь не враждебно, а ярмо новой власти, намного менее обременительное, местные жители охотно предпочли господству деспотических христианских властителей.
Старая провинция Римской империи Африка, которую арабы называли Ифрикией (в нее входили современные Триполитания, Тунис и Алжир), была захвачена мусульманами в 647 году, но лишь спустя пятнадцать лет сопротивление византийского и в особенности берберского населения стало понемногу ослабевать. На завоеванных территориях арабы выделяли три этносоциальных группы. Первая — рум: это слово обозначало главным образом византийцев, то есть подданных Римской империи (от греческого Romaioi), но на африканском побережье к западу от залива Сирт так называли и тех, для кого родным или общеупотребительным языком был латинский. Вторую группу составляли африки´ — коренные жители, уже принявшие христианство. И, наконец, третью — берберы (от латинского «barbarus», варвары), оставшиеся за пределами римской цивилизации, небольшая часть которых относительно недавно стала христианами. Берберы позже все-таки приняли ислам, но так и не были ассимилированы арабами. Как и арабы, они изначально не были мореплавателями, однако помощь сирийских и египетских моряков позволила им вскоре обратить взгляд на Средиземное море. Уже в 665 году мусульмане использовали морскую базу Джалула, отвоеванную у византийцев; в 670 году был основан город Кайруан (на территории современного Туниса), получивший свое название от арабского слова со значением «военный лагерь»; примерно в 700 году был построен хороший порт в городе Тунис, куда перебрались вместе с семьями сотни египтян, сведущих в кораблестроении. А приблизительно пятью годами позже вся северная Африка, включая арабский «дальний Запад» (ал-Магриб ал-Акса), — то есть Марокко — уже была в руках завоевателей; одновременно начался трудный и долгий процесс исламизации и арабизации берберов. В конце июля 711 года большой мусульманский флот под командованием бербера Тарика бин-Зийада захватил бухту Альхесирас на Пиренейском полуострове, на которую еще годом ранее был совершен набег. Арабско-берберские силы насчитывали около 10 000 человек. Разгромив войска готского короля Родериха, захватчики немедленно двинулись к Севилье, затем заняли Кордову и в 713 году — Толедо. Год спустя был завоеван Арагон; примерно к 720 году мусульмане захватили также Каталонию и Септиманию, то есть все территории к югу и к северу от Пиренеев, ранее принадлежавшие вестготам. Захват земель, которые африканские, а вслед за ними и остальные арабы называли ал-Андалус («Земля вандалов»), был столь стремительным, что это пытались объяснить пособничеством евреев, еретиков и врагов Родериха из числа готов.