Изъяны морской стратегии — или ее полное отсутствие — в этот период лучше всего можно проследить на примере Крита, история которого иллюстрирует собой многие социорелигиозные, политические и военные сложности эпохи. Завоевание Магриба и Аль-Андалуса положило конец римско-византийскому влиянию в Северной Африке и Западном Средиземноморье. Однако на протяжении почти всего исламского периода в самом Аль-Андалусе единства не было: страну раздирали этнические и религиозные противоречия между арабами, берберами, сирийцами и новообращенными мусульманами романо-готского происхождения, которых называли мувалладами. В 813 году после кровавой резни пятнадцать тысяч мувалладов бежали из Аль-Андалуса. Примерно половина — по большей части ремесленники из Толедо и Кордовы — перебрались в Марокко. Вторая половина, несмотря на отсутствие морского опыта, отплыла через Сицилию или Ифрикию и Эгейское море в Египет, где «люди, называемые андалусцами, прибыли [в Александрию] с богатой добычей, награбленной на греческих островах». Аббасидский правитель Египта не позволил им остаться или осесть на других мусульманских территориях, так что примерно в 824 году они отплыли на Крит.

Остров плохо оборонялся; кроме того, критяне недолюбливали византийцев, чье правление сопровождалась высокими налогами и поборами. Андалусцы основали свою столицу Аль-Хандак (ныне Ираклион), которая стала процветающим центром независимого критского эмирата. Налоги были умеренные, и из бедной провинции на границе Византийское империи остров превратился в благополучное самостоятельное государство, экспортирующее вино, мед и сыр, а также лес для египетских верфей. Что не менее важно, Крит стал базой, с которой совершались набеги на острова Ионийского и Эгейского морей, материковую Грецию и Малую Азию. Потеря острова, вероятно, произошла из-за неспособности византийцев верно оценить геополитические изменения, происшедшие после завоевания мусульманами Египта, Леванта и Северной Африки. Упускать из виду Крит, не обладая безоговорочной властью на море, — непростительная ошибка для страны, имеющей стратегические интересы в данном регионе: стоит власти ослабнуть — и остров станет добычей держав-соперниц.

Критский эмират процветал независимо от материковых государств. Хотя у мусульман был общий враг — христианский Константинополь, политические разногласия между Аббасидами и новыми династиями на Западе исключали согласованность действий. Яркий пример тому — события, последовавшие за дерзким набегом мусульманина Льва Триполитанского на Фессалоники, второй по значимости город империи, в 905 году. Учитывая стратегическое положение острова и опыт критян в борьбе с Византией, разумно было бы обратиться к ним за помощью и советом. Однако Лев, возвращаясь в Триполи (Ливан), не сообщил критянам о своем намерении, и те приняли его флот за византийский, идущий захватить остров. Ошибка вполне понятна, учитывая, что Константинополь по крайней мере четырежды безуспешно пытался отбить Крит у мусульман.

Византийцы отвоевали Крит лишь спустя более полувека после набега Льва на Фессалоники. Судьбу острова в конечном счете решил разлад между мусульманскими государствами. Фатимиды были заняты покорением Египта и не думали о стратегическом значении острова для себя и для Дар аль-Ислама в целом. Мусульманские правители проявили ту же недальновидность, что византийские в IX веке, и как следствие баланс власти в Восточном Средиземноморье полностью изменился. В 961 году Никифор Фока захватил остров, а четырьмя годами позже, уже в качестве императора, положил конец трехсотлетнему совместному владению Кипром. Никифор и его преемники объединили под византийским правлением значительную часть Сирии и Леванта — впервые с 640-х годов. Впрочем, их попытки вернуть Сицилию не увенчались успехом, и остров целое столетие процветал под властью арабской династии Кальбитов. Фатимиды не отказались от своих интересов в Италии и призывали Кальбитов на помощь в войне с Омейядской Кордовой. В 950-х годах Кальбиты совершили набег на Аль-Андалус, но их флот был гораздо слабее омейядского, и Абд ар-Рахман III ответил набегами на Ифрикию.

Эти примеры показывают неверность укоренившегося взгляда, будто Средиземноморье делилось на монолитные сферы влияния: христианскую и мусульманскую. В действительности мусульманский мир был политически раздроблен. Это явствует не только из хроники военных событий, но также из расширения торговли между Византией и мусульманскими портами в XI веке и многообразия предметов на затонувшем судне из Серче-Лиманы. Международные отношения в XI веке и позже еще более осложнятся расколом между греко-православным Востоком и римско-католическим Западом в 1054 году, а после — появлением новых морских держав, которые совершенно изменят характер средиземноморской торговли.