Арабские завоевания шли под знаменем новой религии — ислама. Исламизированное население тоже включалось в ряды завоевателей. В Африке таким населением были берберы, отказавшиеся от сопротивления и принявшие ислам, а постепенно и арабский язык. Именно исламизированные и арабизированные берберы и составляли основную часть войска новых завоевателей, тех мавров, под именем которых испанцы знали своих новых господ.
Захват арабами Северной Африки, особенно Карфагена, долгое время бывшего главным пунктом связи Испании со средиземноморским миром, привел к окончательной изоляции Испании, прервав ее контакты с Центральным и Восточным Средиземноморьем. Падение Карфагена и угроза нового врага, по-видимому, заставили вестготских королей снова попытаться укрепиться на африканском берегу пролива. Такую попытку уже делал в свое время Тевдис, захватив на какой-то момент Септем (Сеуту). Однако вестготы были оттуда выбиты византийцами и больше таких попыток не предпринимали. Падение византийской власти предоставило вестготам возможность повторить экспедицию. В начале VIII в. эта крепость уже находилась в руках вестготов и управлялась вестготским графом. Септем должен был прикрыть Испанию от возможного арабского вторжения.
Именно септимский граф Юлиан вошел в историю как виновник арабского вторжения в Испанию. Поведение Юлиана полностью «вписывается» в рамки политической борьбы, развернувшейся в Испании после смерти Витицы. Юлиан принадлежал к группировке, поддерживавшей сыновей покойного короля. Согласно другой версии, арабов призвали в Испанию непосредственно сыновья Витицы, которые направили в Африку послов с просьбой помочь им свергнуть Родриго и вернуть семье покойного короля трон. Впрочем, обе версии не противоречат друг другу, и очень вероятно, что и обращение сыновей Витицы, и предательство Юлиана были следствием единого заговора.
Сыновей Витицы мог вдохновлять пример Атанагильда, который в свое время ради борьбы с королем Агилой призвал на помощь византийцев, а позже, укрепившись, начал войну с теми же византийцами. Они считали, что мусульмане не собираются завоевывать страну и ограничатся только полученной там добычей. Но на этот раз дело обернулось совершенно иначе.
Арабский халифат находился в расцвете своих сил. Халиф Абдальмалик провел ряд реформ, приведших к преобразованию Халифата в военно-бюрократическое государство. После некоторого перерыва, вызванного междоусобными войнами, арабы возобновили свои завоевания. Был захвачен Карфаген. Арабская армия под командованием Мусы ибн Нусайра подчинила бо́льшую часть современного Марокко, выйдя к побережью Атлантического океана. К Мусе и обратились за помощью сыновья Витицы, с ним повел переговоры Юлиан, даже признавший власть арабского наместника.
Арабы уже давно знали о существовании Испании как самой западной части средиземноморского мира. Известна она была и под названием Spania (по-видимому, заимствованному у византийцев), но, вероятно, еще до завоевания появилось у них и постепенно ставшее наиболее распространенным другое название — аль-Андалус, происходившее от имени вандалов, владевших когда-то частью Испании. Захват Северной Африки позволил арабам сделать следующий шаг — попытку распространить ислам и свою власть и на европейскую часть Средиземноморья. И в этих условиях совершенно естественным представлялся переход с африканского на европейский берег пролива.
Осенью 709 г. арабские корабли совершили рейд на испанское побережье, и ее успех побудил Мусу счесть завоевание Испании не таким уж трудным делом. В 710 года уже отряд во главе с Тарифом ибн Маликом на кораблях, предоставленных Юлианом, захватил небольшой плацдарм на испанском берегу, откуда было совершено несколько набегов на окрестности. В результате этих набегов арабы захватили богатую добычу, и Муса, вдохновленный этой добычей, стал готовить уже большую экспедицию. Извещенный об этих событиях, халиф Валид, не решаясь предпринять большую заморскую экспедицию, приказал Мусе ограничиться разведкой, но тот, ссылаясь на то, что арабские владения отделяет от Испании не море, а только пролив, стал готовить большое вторжение.