Век, в котором возник халифат, завершился установлением мусульманского владычества над древним Карфагеном. Отнятый у Византии 40-тысячной сухопутной армией под командованием ал-Хасана ибн Нумана в 696-м, Карфаген в следующем году был отвоеван обратно, однако вмешательство арабского флота в 698 году позволило ал-Хасану нанести противнику решительное поражение на суше и на море. К этому же времени относится захват арабами острова Пантеллерия между Карфагеном и Сицилией. Опираясь на завоеванные плацдармы, арабские корабли все больше оспаривали византийское господство на Средиземном море. Этой цели служили многочисленные набеги из Сирии, Египта, Кайрувана и Сеуты на подвластные Константинополю средиземноморские острова. Таким образом, продвижение арабских армий на запад ставило под удар все новые византийские владения. Удаленность владений от метрополии возрастала, и это делало их возможной добычей арабов. Активность арабского флота на Средиземном море отвлекала Византию от давления на пограничные линии в Сирии, и вот почему даже позже, в IX веке, когда на североафриканских территориях халифата возникли самостоятельные династии, багдадские Аббасиды были заинтересованы в союзе с ними и поощряли их морскую деятельность. Благодаря этому сирийские пограничные линии, построенные в 786 году, несмотря на постоянные арабо-византийские войны, смогли просуществовать 140 лет: они были прорваны лишь в 926 году.
В начале VIII века, овладев Сеутой, арабские полчища дошли до Атлантическото океана. Чужие безбрежные воды «Темного моря» уходили в непроницаемую даль, преграждая завоевателям дальнейшее движение на закат. Остановленные самой природой, они хлынули к северу. Византийский правитель Сеуты Юлиан, вступив в соглашение с арабами, передал им свои корабли, на которых в 710 году первая группа мусульманских войск под командованием вольноотпущенника ат-Тарифа переправилась на пиренейский берег. Парадокс? Да, но дело не только – и не столько, – в чувствах оскорбленного отца, юная дочь которого обесчещена на ложе вестготского короля Испании. Соперничество в странах средиземноморского рынка, вырывшее глубокую пропасть между вестготами и Византией, куда существеннее в ряду причин решения Юлиана, и при этой розни его стремление обратить завоевательную активность арабов против страны на другом берегу Гибралтара вполне понятно.
Группа ат-Тарифа состояла из 400 воинов и 100 лошадей. Переправившись на четырех кораблях, отряд опустошил Алхесирас и в июле того же 710 года вернулся в Сеуту. Но уже в следующем году другой вольноотпущенник, Тарик ибн Зияд, имя которого увековечено в названии Гибралтара, переправился на берег Испании во главе семи тысяч воинов, а оставшийся в Сеуте наместник Муса ибн Нусайр приступил к ускоренному строительству десантных кораблей. Когда Тарик, узнав о том, что вестготский король Родерих движется против него во главе большой армии, запросил подкреплений, Муса уже имел столько судов, что мог перебросить в Испанию пять тысяч берберов. Всего через год, в июне 712-го, сам Муса переправился на пиренейский берег во главе уже 18-тысячного отряда. Теперь даже здесь, на далеком западе, арабы владели значительными военно-транспортными средствами, и легкой дымкой легенды подернулось воспоминание самого старшего поколения о том, как три четверти столетия назад воины халифа Омара, штурмуя персидскую столицу Мадаин, за неимением речных транспортов для перевозки войск форсировали Тигр вплавь на конях.