Морская коммерция распространила иудаизм, ислам и христианство по всему Средиземноморью, в точности как морская торговля способствовала проникновению буддизма из Индии и Шри-Ланки в Юго-Восточную Азию и Китай. Общность веры объединяет народы, однако расколы зачастую подрывают религиозные связи. Христианство стало государственной религией Византии, но сильно политизированные догматические разногласия привели к гонениям на коптов и христиан-несторианцев. В итоге, когда в 610-х годах персы-сасаниды вторглись на Левант, копты и несторианцы поддержали их, сочтя, что уж лучше персы, чем константинопольские христиане. Сасаниды заняли Дамаск, Антиохию, Иерусалим и Александрию, а в 626 году встали лагерем в Халкидоне (ныне Кадыкей, Турция) через Босфор от Константинополя. Впрочем, дальше им продвинуться не удалось. Тремя годами позже византийцы захватили персидскую столицу Ктесифон на Тигре, а византийский флот отвоевал сирийские и египетские порты. После разгрома персов Византия осталась самым большим и прочным государством Средиземноморского бассейна.

За схваткой враждующих империй мало кто заметил появление пророка Мухаммеда, однако уже в 635 году его последовали захватили Дамаск, а затем разбили византийскую армию в битве на реке Ярмук (между Иорданом и Сирией) и таким образом освободили семитское население Леванта от почти тысячелетнего эллинистического-римского-византийского правления. Повернув на восток, арабы захватили Ктесифон, а к 642 году арабское войско подошло к Индии — то был завоевательный поход, достойный Александра Македонского и имевший куда более долгие последствия. На западе Амр ибн аль-Ас основал Фустат (впоследствии Каир) в дельте Нила и захватил Александрию.

Овладев средиземноморскими портами, арабы получили корабли и опытных моряков, что позволило им атаковать Византию с моря. Поначалу халифы стремились захватить византийские земли в западной части средиземноморского бассейна. Подчинив себе порты Египта и Сирии, арабы получили возможность угрожать Кипру и самому Константинополю. В конце столетия Омейяды захватили византийскую провинцию в Африке, которую назвали Ифрикией; она стала плацдармом для наступления на Северную Африку и Пиренейский полуостров. Сицилия пала в IX веке, примерно тогда же, когда изгнанные из Аль-Андалуса арабы создали независимый эмират на Крите. Во всех этих случаях христианское правление сменялось мусульманским, однако и христианский, и мусульманский мир раздирали политическая вражда и внутрирелигиозные расколы, что создавало богатые возможности для сотрудничества между христианами, мусульманами и иудеями.

Исламская морская экспансия началось в 648 году, когда правитель Египта Муавия ибн Абу Суфьян с флотом из тысячи семисот кораблей обложил жителей Кипра ежегодной данью. Семью годами позже, когда киприоты предоставили Византии корабли, он захватил остров, положив начало первому морскому конфликту между империей и халифатом. Император Констант II, потеряв Кипр, собрал флот размером от семисот до тысячи кораблей, чтобы захватить порт Феникс на побережье Ликии севернее острова. Сохранившиеся отчеты о сражении противоречивы, но все сходятся в одном: в битве Мачт (Зат ас-Саварн), которую христианские авторы называют битвой при Фениксе, мусульмане одержали безоговорочную победу. Она показала, что мусульмане могут сражаться на море, однако внутренние раздоры внутри халифата не давали арабам закрепить успех, пока Муавия не стал первым Омейядским халифом.

В 678 году Омейяды начали десятилетнюю осаду Константинополя, во время которой заняли базу флота на Мраморном море, но не смогли захватить византийскую столицу. В конечном счете была достигнута договоренность, включавшая демилитаризацию Кипра: киприотов обязали соблюдать нейтралитет в любых конфликтах между империей и халифатом. Остров стал промежуточной остановкой для купцов, пассажиров, военных флотов и лазутчиков. Хотя киприоты оставались христианами, двоякий статус давал мусульманским военачальникам стратегическое преимущество против Византии, что отмечали и мусульманские, и христианские авторы. В «Тактике» (примерно 900 год) император Лев VI писал: «…пока варвары собираются вместе против ромейского [то есть византийского] войска из Египта, Сирии и Киликии, следует объединить силы морских стратигов с морским флотом Кипра». Арабский автор X века подтверждает, что первым этапом всякой морской экспедиции против Византии был сбор кораблей в кипрских водах. Кипр оставался в совладении до полного восстановления власти Византии в 965 году.

Еще до осады Константинополя мусульманские войска захватили всю Северную Африку — Билад аль-Магриб, или Закатные земли — до Ифрикии. В 695 году Карфаген пал под натиском арабской армии, однако новый правитель счел порт слишком плохо защищенным от нападения с моря и основал новый неподалеку, в Тунисе, в почти неприступном месте — на озере, отделенном от моря узким перешейком, в котором арабы прорыли канал. Византийцы не делали попыток отбить Карфаген из-за внутренних разладов в Константинополе, где с 695 по 717 год сменилось семь императоров. В 717 году Омейяды начали крупное наступление и продвигались без помех, пока на трон не взошел Лев III Исавр, который укрепил стены Константинополя, собрал припасы и натянул цепь через устье Золотого Рога — первый известный случай применения такой меры. Несмотря на флот в тысячу восемьсот кораблей и большое войско, Омейяды не смогли перекрыть Константинополю доступ к черноморским житницам и сняли осаду.

Этот неуспех не помешал продвижению Омейядов в Северной Африке. Основав Тунис, Муса ибн Нусайр повел арабо-берберское войско в Танжер, а в 711 году двенадцатитысячная армия под предводительством Тарика ибн Зияда переправилась через Гибралтарский пролив и высадилась у скалы, получившей в его честь имя Джабаль аль-Тарик, или Гибралтар. Муса и Тарик двинули свои войска на север к реке Тахо, Толедо, Таррагоне и Барселоне. Они дали захваченным землям название Аль-Андалус и учредили столицу в Севилье, примерно в восьмидесяти пяти километрах вверх по Гвадалквивиру от Атлантического океана. Хотя через сорок лет столицей стала Кордова, Севилья оставалась важным военным и торговым портом и при мусульманских, и с XIII века христианских правителях. Аль-Андалус стал первой частью мусульманского мира, решительно порвавшей с политическим главенством халифата. В 750 году Абуль-Аббас ас-Саффах основал Абассидский халифат. Он перебил почти всех членов Омейядского рода, кроме Абд ар-Рахмана I, который бежал на запад и основал независимый Омейядский халифат Аль-Андалуса. Даже безотносительно такого явного разрыва Аль-Андалусу предстоял отдельный исторический путь. Тому было несколько причин: близкий и продолжительный контакт с латинской Европой, географическое положение на двух сторонах Гибралтарского пролива, набеги викингов и в целом враждебные отношения с Ифрикией и мусульманской Сицилией.

Самый ранний мусульманский набег на Сицилию датируется 652 годом, однако настоящее завоевание началось лишь в первой половине VIII века, когда корабли из Ифрикии начали нападать на Сицилию, Сардинию и Балеары. В конце VIII века Карл Великий отозвался на просьбу Балеарских островов защитить их от мавров, и в следующие тридцать лет архипелаг был базой для франкских кораблей, несущих дозор меджу Италией, Сардинией, Барселоной и франкским побережьем.

Интерес франков к Северной Италии усилился после того, как захват Ломбардского королевства и попытка Карла Великого присоединить к своим владениям Венецию привели к столкновению с Византией в 806 году. Венецианские купцы были формально подданными Константинополя, но хотели торговать с франками; мирный договор 812 года подтвердил статус Венеции как византийской территории, однако разрешил ее гражданам торговать с франками и обязал их помогать франкам в борьбе с пиратами в северной части Адриатического моря. Под защитой двух великих держав военный и торговый флот Венеции неуклонно увеличивался.

Франко-византийская вражда и тот факт, что Византии пришлось бросить значительную часть флота на отражение булгарской угрозы в Черном море, открыли дорогу ифрикийскому завоеванию Сицилии. В 800 году аббасидский халиф Гарун аль-Рашид назначил эмиром Ифрикии Ибрагима I ибн аль-Аглаба, первого из автономных аглабидских эмиров, правивших в течение столетия. Одной из главных задач Ибрагима стало создание флота для защиты ифрикийской торговли. Через год после разрешения венецианского кризиса византийский стратиг Сицилии достиг с мусульманскими послами соглашения, по которому купцы одной страны могли заходить в порты другой, а чуть позже правители христианского Неаполя попросили у Аглабидов помощи против соседнего герцогства Беневенто. Мусульманские войска, высадившись в Италии, разбили врагов Неаполя на обоих побережьях и захватили контроль над заливом Отранто; их корабли дошли на севере до устья реки По и Истрии (современная Словения) на противоположном побережье от Венеции.

Аглабиды начали совершать набеги на Сицилию в 820-х годах, но закрепились на острове лишь после того, как поддержали мятеж против византийского морского стратига. Экспедиционный корпус в 70–100 кораблей, на которых находились десять тысяч воинов, отплыл из Туниса летом 829 года, а двумя годами позже Аглабиды захватили Палермо. Переименованный ими в аль-Мадину, он стал столицей, главной военно-морской базой и коммерческим центром нового эмирата. Завоевание острова продолжалось до конца столетия: Сиракузы пали в 878 году, Таормина в 902-м. Все это время Аглабиды продолжали наступательные действия в Адриатике. В 866 году они осадили Рагузу (Дубровник, Хорватия), но город спасло неожиданное появление ста византийских кораблей, которые перетащили в Адриатическое море волоком по древним диолкам через Коринфский перешеек, вероятно, чтобы избежать встречи с критским и аглабидским флотами в Эгейском море и заливе Отранто. В следующие три десятилетия византийские, каролингские и аглабидские силы сражались за контроль над Южной Италией и Адриатикой, но к началу X века Мессинский пролив стал фактически демаркационной линией между мусульманской Сицилией и христианской Италией. Неаполь, Амальфи и другие южноитальянские порты, оказавшиеся между двумя воюющими державами, всячески избегали конфликтов с мусульманской Сицилией. Купцы из Амальфи, имевшие давние торговые привилегии в отношениях с Константинополем, между IX и XI веком, успешно используя нейтралитет и географическое положение своего города, стали посредниками между королевствами Западной Европы, мусульманской Северной Африки (особенно Египта) и Византийской империей. Амальфитяне «славились почти по всему миру», а их порт, место встречи «арабов, ливийцев, сицилийцев и африканцев», считался «самым процветающим городом в Ломбардии, благороднейшим и прекраснейшим, самым богатым и изобильным». Мусульманская власть в Средиземноморье достигла зенита в начале X века, когда тот или иной эмират либо халифат полностью или частично владел Кипром, Критом, Сицилией, Мальтой и Балеарскими островами, а в Эгейском море Паросом и Наксосом в Кикладском архипелаге к северу от Крита и Эгиной неподалеку от Афин. Из крупных средиземноморских островов лишь Корсика оставалась под властью христианских правителей. Но хотя Дар аль-Ислам рос, мусульмане были так же далеки от внутреннего единства, как и христиане, — этот факт имел особую важность для баланса морского господства в Средиземноморье. На западе Омейяды правили в Испании и расширили свои владения за счет Балеарских островов, которые остались под властью мусульман на следующие три века. Марокко принадлежало трем мелким эмиратам, а аглабидские правители Ифрикии пользовались значительной свободой действий в Северной Африке, на Мальте и на Сицилии. Дальше на восток Критский эмират был полностью независим; Кипр находился в совместном владении мусульман и Византии, а в Египте с 868 по 905 год правила династия Тулунидов.

Меньше чем за столетие картина изменилась бесповоротно. Аббасидский халифат распался из-за внутрирелигиозных несогласий. Сирия в 906 году досталась шиитским Хамданидам из Ирака, Ифрикия тремя годами позже — шиитским Фатимидам, а Египет, во второй раз — недолговечной династии Ихшидидов (935–969), которые, как и Аббасиды, были суннитами. Тем временем на западе Абд ар-Рахман III окончательно порвал с остальным мусульманским миром, объявив себя халифом, то есть преемником Мухаммеда, а не просто военачальником или правителем. Омейядский халифат Кордовы не надолго его пережил, и к концу века Аль-Андалус и Балеарские острова были разделены между тридцатью независимыми микрогосударствами, так называемыми «тайфами». Самым значительным из этих событий было воцарение Фатимидов, свергших Аглабидов в Ифрикии и на Сицилии. В 921 году они основали новую столицу примерно в девяноста милях севернее Туниса, в порте Махдия, который стал базой для рейдов на Италию, Францию, Испанию и острова от Мальты до Балеар. Затем Фатимиды завоевали Египет и значительную часть Леванта, а их новая столица в Каире (Эль-Кахира, «Победоносная», основанная в 969 году) быстро затмила Багдад, став коммерческим и политическим центром мусульманского мира, что имело значительные последствия для торговли в Средиземноморье и в муссонных морях. Центр тяжести мусульманского мира переместился из верховьев Персидского залива и Багдада в Восточное Средиземноморье, и при этом правящие Фатимиды были всерьез ориентированы на морскую торговлю, — однако для средиземноморских морских путей появление фатимидского Египта обернулось не триумфом, а катастрофой.