1513年2月，阿尔布开克终于从果阿起航，向红海进军。

此时，他的战略构思囊括了半个地球，印度已不再是他的目的，而是扩张基地。他最终要消灭伊斯兰世界，收复耶路撒冷，让天主教统治天下。

他的第一个目标是攻占亚丁，这样既可以为进出红海提供一个安全基地，又可以对印度洋形成最终的包围之势。4月22日，耶稣受难节，葡萄牙舰队抵达亚丁，它的港口是新月形，里面停满船只，卡瑞克帆船太大，只能停在港外。远远望去，亚丁让人生畏，它处在一座死火山口，四周环绕着九座寸草不生的紫红色岩石山，每座山顶都有一座要塞。

亚丁总督米尔（Aamir Mir）派出一名信使，礼貌地询问来客有何贵干，并送去食物做见面礼。阿尔布开克直截了当，说要去苏伊士运河和吉达消灭埃及舰队。他拒绝接受总督送来的食品：“我的习惯是，不接受尚未与我们缔结和约的国家和君主的礼物。”他要求米尔打开城门，让他的士兵进去。信使提议，让总督亲自来谈判，阿尔布开克说没有意义。于是，士兵们摩拳擦掌，磨刀霍霍。

兵贵神速，阿尔布开克必须在沙漠援兵赶来之前把亚丁拿下。

第二天凌晨，军号响过之后，士兵们登上小船，划到浅滩停下，然后涉水上岸，他们浑身湿透，火枪手的火药被水打湿。(www.daowen.com)

为争夺第一个登上敌城的荣誉，他们不畏穆斯林守军的箭和石块，争先恐后地爬上攻城的长梯。城墙很高，梯子不够长，爬到顶端的人再爬城墙的时候速度变慢了，可底下一大群人闹哄哄地在跟进，长梯上便出现了拥塞。看到梯子快承受不住了，阿尔布开克命令戢兵从底下去支撑梯子。但梯子还是倒了下来，戢压断了，戢兵被砸成重伤。

此时，已经登上城墙的人感到没有后援，决定撤退，但他们没有梯子可以爬下来。城下的葡萄牙士兵向上投掷绳子，协助他们下城墙。穆斯林士兵夺回城墙上的塔楼，把葡萄牙人的头颅插在长枪上，向下挥舞。

葡萄牙人试着撞开主城门，但怎么也撞不开。最后他们用火药把城墙炸出一个大洞，可指挥官不敢带头进去，士兵们也只是在原地逡巡。

这是一个关键性错误，如果他们冲进去，可能一口气占领亚丁。

但葡萄牙人没能攻破城池，只好撤退，亚丁战役失败了。