进攻克里特岛的重要问题之一是迅速提供重型武器。完成这项任务的唯一理想途径是用机帆船与商船从海上运进武器。德军企图执行这项任务并同时阻止英国海军把援兵送上克里特岛的军事行动，导致了第二次世界大战第一次“海空之战”。很明显，英国人在空中处于劣势，他们希望使用能够在东地中海投入作战的强大的海军部队来弥补这个不足。英军认为，德国人将会发现单靠空军夺取克里特岛是不可能的，所以估计大量德军将试图从海上登陆。
第8空军军已经收到了如下指令：在作战的准备阶段要不断地监视克里特岛周围的海面，并袭击在这一海域中看到的所有运输舰。第8空军报告称，在执行这项指令中，到5月20日止，已击沉或重创27艘敌舰船。
两支由机帆船编成的船队根据计划从比雷埃夫斯与哈尔基斯驶出，由意大利的“狼”号与“人马座”号鱼雷艇护航，载有一支约2300人的山地部队和重装备，在进攻克里特岛的当日夜间，抵达了战斗出发地点——梅洛斯岛。第4航空队要求东南舰队司令竭尽全力保证第一支船队于5月21日夜幕降临前，在马利姆附近靠岸。德国当局还试图说服意大利舰队出海，以便把参加克里特岛作战的英国海军部队引开，但是被拒绝了。
5月20日至21日夜，英国海军部队绕越在其东侧的克里特岛，又穿过该岛西侧的基西拉海峡，搜索了克里特岛以北的海域，并沿该岛北部的海岸巡戈。英国海军在搜索过程中，轰击了斯卡潘托机场，但未造成很大的破坏。正在待命出击的攻击力量强大的第八空军看到时机已到，于是在5月21日晨向正在撤离的英国海军舰队发起攻击，击沉“大后”号驱逐舰，重创“阿贾克斯”号巡洋舰。当时仍在该岛以南进行战斗的第8空军于上午9时报告说，克里特岛以北的海域已没有敌人的海军部队。接近中午，第一支由机帆船编成的船队继续从梅洛斯岛向马利姆行驶，可是下午被英国皇家空军侦察机发现了。夜间，遭到新抵达的英国海军部队的攻击，这支部队包括“狄多”号、“奥赖恩”号和“阿贾克斯”号巡洋舰以及四艘驱逐舰。多亏意大利“狼”号鱼雷艇（艇长米姆贝利）的英勇奋战（直接中弹18发）和船队的迅速四下疏散，只有十艘舰只被击沉。其余的船只则在伯罗奔尼撒半岛的南海岸避难。关于如何将重型武器与援兵运入克里特岛的问题仍未解决。第2支船队在5月22日清晨又遭到英国第2支特混舰队（其编成内有“佩思”号、“水中仙女”号、“加尔各答”号、“卡莱尔”号巡洋舰和两艘驱逐舰）的攻击而被立即召回。两艘船被击沉。只是由于意大利的“人马座”号鱼雷艇（艇长西加拉）的救援与德国空军立即实施的多次攻击才使损失减少到如此小的程度。为了支援正在发动进攻的海军舰队，坎宁安海军上将派出了第3支特混舰队，其编成内有“厌战”号与“勇士”号战列舰、“格洛斯特”号与“斐济”号巡洋舰以及7艘驱逐舰。5月22日一整天，英国特混舰队与由第10空军的轰炸机和俯冲轰炸机支援的第8空军展开了连续的激战。“格洛斯特”号与“斐济”号巡洋舰以及“快轮”号驱逐舰被击沉。“水中仙女”号巡洋舰、“厌战”号战列舰被重创。“卡莱尔”号防空巡洋舰与“勇士”号战列舰受创较轻。英国海军就是这样付出了高昂的代价才赢得战胜德国运输船队的胜利。翌日，即5月23日，得到加强的第八空军发动的攻击使英国在克里特岛以南海域又损失了两艘驱逐舰——“卡西米尔”号与“凯利”号。德国空军首脑对于英国人是否会把这场在“狭窄的海域飞机对军舰”的作战的胜利让给他们仍无把握。但是，5月24日坎宁安海军上将坦率地向伦敦报告，他的部队迫于德国空军攻击的巨大压力，昼间已不能在爱琴海或克里特岛周围水域作战。任何企图阻止敌人把部队与补给物资从海上输送登陆的做法都必然会使东地中海舰队蒙受惨重的损失。然而，伦敦对于德国人将会发现他们不可能从空中夺取克里特岛（尤其是他们只占领了一个飞机场——马利姆飞机场）这一点还相当有把握，因此坎宁安在亚历山大港得到的答复是决不妥协，英国海军与皇家空军必须不顾一切风险阻止德国人将更多的援兵送入克里特岛。根据这项指示，英国海军舰队必须在昼间实施消灭该岛以北的德国运输船队的作战，并准备蒙受巨大的损失。但是，尽管英国当局发布了这些指示，却不可能把更多的战舰从西地中海调往克里特岛。因为驻守在直布罗陀的“H11舰队、本土舰队的全部舰只以及其他所有可以使用的舰只都被动员用于猎捕德国傅斯麦”号战列舰了，该舰正在大西洋中“逍遥法外”。
尽管如此，5月24日至25日，英军夜间增援克里特岛北部沿海的活动仍在继续进行。5月26日，甚至“可畏”号航母也出现在那里，并以12架舰载飞机袭击了斯卡潘托岛上的机场。当天下午，它遭到德国轰炸机的猛烈轰炸，右两处直接中弹，与此同时“努比亚人”号驱逐舰被炸掉了尾。次日，隶属另一支特混舰队的“巴勒姆”号战列舰在卡斯岛东南水域因遭到攻击而受创。
所有这些作战行动都十分清楚地表明，在占优势的敌空军飞机的航程内，一个舰队如果没有充分的空中掩护是不能实施海上作战的，否则就要付出十分高昂的代价。
