为了果阿战役而临时改变行程的瓦斯康塞洛斯，想到了他的使命，他急切希望启程去马六甲。但他又焦虑地想到，如果没有阿尔布开克的帮助，他的四艘船根本不可能成功。这一次换成他去动员阿尔布开克，他没想到，阿尔布开克比他好说服。

1511年4月，阿尔布开克率领能召集来的全部力量，陪同瓦斯康塞洛斯出征马六甲。他的舰队一共18艘船，其中12艘是卡瑞克帆船。他要跨越东印度洋，假如遇到困难，在他航行的2400公里中，很难找到歇脚点。

阿尔布开克按照阿劳若的建议，一路俘虏穆斯林船，烧杀抢掠，散播恐怖。

这是一片陌生全新的海洋，已经看不见西印度洋的阿拉伯三角帆船，取而代之的是苏门答腊岛、爪哇岛、中国的平底船，它们是巨大的四桅帆船。阿尔布开克的旗舰海洋花号已经甚是雄伟，但他遇到一艘比海洋花号还高大的平底船，它有三四层重叠的甲板，大炮似乎奈何不了它。一连两天，它在葡萄牙人的炮火中逃跑，直到它的舵被打飞，丧失了动力，才不得不投降。阿尔布开克也损失了一些船，旗舰船龄已经九年，适航性越来越差。

最后，他们咄咄逼人地造访了苏门答腊岛上那些臣属于马六甲的小国，7月1日抵达马六甲。阿尔布开克在城市前方停船，放下锚，没有开炮，等待国王派使者来岸边会晤。

马六甲有宏伟的高墙环绕，比里斯本大多了，人口超过12万。马六甲控制着往来印度洋的海路，人称“太阳眼”。它是当时最国际化的城市，在那里可以听到84种语言。跟它比起来，印度像是穷乡僻壤，欧洲不值一提。所以葡王想要的，不仅仅是营救人质，他最想要的是马六甲的财富。(www.daowen.com)

马六甲总督穆罕默德（Muhammad）提出，必须先签订和平协议，共同维护安全通航，然后再交还葡萄牙人质。阿尔布开克寸步不让，不还人质，这里没有安全可言。在古吉拉特和爪哇穆斯林的鼓动下，穆罕默德决定拖延谈判，等待季风变换，迫使葡萄牙人自动离开。阿尔布开克不耐烦了，他炮击城市，烧毁海边房屋和古吉拉特平底船，迫使穆罕默德慌忙回到谈判桌上。

穆罕默德让人质换上华丽的衣服，把他们全部交还阿尔布开克。但阿尔布开克提出了额外条件，要求马六甲重金赔偿葡萄牙蒙受的损失，还要求建造一个防御要塞和贸易站。穆罕默德支吾搪塞，私下里开始在最敏感的跨城大桥两端建造坚固的防御工事，以防止阿尔布开克切断城市。

马六甲的战略关键正是河上那座大桥，夺取它，马六甲就会被切成两半儿。

阿尔布开克决定兵分两路，一路由他自己率领，在河东岸登陆，那里是马六甲的主要部分；另一路在河西岸登陆，那里有总督府和一座清真寺，两路人马最后在大桥会合。