但是，到了1530年，卡洛斯想起自己的属国当中有三个浮在地中海的岛屿，即马耳他岛及其附属的两座小岛。皇帝也许认为，如果是马耳他岛的话，送给骑士团也无妨。谈判得以成立，条件是一年上贡一只猎鹰作为地租。但是，只要骑士团把马耳他作为领地，就属于西班牙国王的臣下，将有义务攻下北非的的黎波里。
这清楚地表明了卡洛斯打算如何利用圣约翰骑士团。同时也是西班牙国王的卡洛斯曾有野心想把阿尔及利亚和突尼斯等北非地区变成自己的领地。而且，让圣约翰骑士团驻守马耳他也可以保护自方的船只免受以那一带为根据地祸害周围地区的海盗的侵害。海盗们得到了缺乏海军力量的土耳其帝国的认可，被允许拥有作为根据地的土地和港口，行使主权，条件是，战时必须加入土耳其海军与其共同作战。
但是，如果将无论如何都属于西地中海的马耳他岛作为根据地，就再也无法声称处于针对异教徒的最前线。罗得岛是真正的最前线，但在马耳他，对手是海盗，只能成为卡洛斯的帝国看门狗。
骑士团大团长也对此心知肚明。但如果拒绝这个提议，就不知在何时何地能得到根据地了。即便存在理由是击退海盗，也是必要的。因为拥有根据地并恢复存在理由是防止骑士团灭亡的唯一途径。
1530年，被赶出罗得岛8年之后，骑士团迁往马耳他定居。
但是，对习惯和熟悉玫瑰花盛开的古老岛屿的骑士们来说，马耳他岛足以让他们彻底失望。
首先，气候十分恶劣。由于全岛都是秃山，冬天的严寒和夏天的酷暑都痛苦难耐。这是一座好像被人忘却的岛，居民只有1万多人，几乎都是文盲，说的是阿拉伯语的方言。这可能是500年前纳入阿拉伯统治之下的历史与距离北非较近的位置所致。在贫穷的居民中，少数上流阶层是统治西西里岛的西班牙裔，他们能说一点西班牙语、意大利语和法语。总而言之，在马耳他岛完全无法期待罗得岛温暖的气候、以绿色为底色的丰富色彩以及到处弥漫的文明的留芳遗香。
但是，骑士团迁往马耳他一事，导致各队都有数名骑士退出骑士团。这些人的主张是，在马耳他岛，圣约翰骑士团会失去存在理由。他们认为只充当卡洛斯的看门狗是一种耻辱。在过去讨论罗得岛是否应开城的会议上，以此为由主张彻底抗战的拉·瓦莱特则留在了骑士团。也许在这个法兰西的年轻骑士心中，深深地印刻着与他同龄的土耳其胜利者的身影。
骑士团大团长在移居马耳他岛4年后，在这座岛上去世。大概从这时开始，马耳他岛的情况逐渐发生了变化。
圣约翰骑士团在马耳他岛必须一切都从头构建。在罗得岛定居前，岛上已经有拜占庭时代的遗迹，骑士团起初只是对遗迹加以利用，随着时间的推移和经费的落实，通过增建、改造或加固，建成了地中海最强的城塞。相比之下，这种模式在没有任何古代或中世纪遗迹的马耳他岛就无法复制了。但是，在圣约翰骑士团的骑士们看来，而且从当时的常识来看，没有城塞的生活方式简直不可想象。荒岛马耳他所拥有的几乎可以称为唯一的有利之处，是有几处仿佛将岩石锐利地凿开了一样的海湾。如果进行妥善建设的话，应该能变成在地中海也屈指可数的良港。
骑士们在没有任何人居住的一带开始建设要塞。这次制订计划并指挥实际施工作业的也是意大利筑城工程师。亚当去世的时候，要塞建设还处于好不容易刚刚起步的阶段。但是，他之后的几代骑士团大团长均承袭了亚当的思路，并全力以赴使其得以光大和发展。1557年，移居马耳他岛27年之后，海湾一带的要塞建设已经完成了一半。骑士团的计划是将伸出海湾的全部八个半岛逐个建设成要塞。在骑士团的财政状况也不如以前那么充裕的马耳他岛时代，这可不是能在短期内完成的事业。
与骑士团一道离开罗得岛的工程师马尔蒂嫩戈没有参加马耳他岛的要塞建设。但他并没有与骑士们分道扬镳。
在罗得岛攻防战中负伤，右眼总是戴着眼罩的威尼斯工程师在骑士团撤出罗得岛后，被骑士团大团长亚当封为骑士。这是对他在攻防战中所做贡献的回报，作为一个没有“蓝色血液”的人，这实属罕见。由于他也是为了参加获得马耳他岛的谈判而被派遣到卡洛斯身边的骑士之一，因此可能有一段时间曾与成为难民的骑士团共同行动。
但是，他没有去马耳他岛，而是推荐了几位工程师前往马耳他岛。马尔蒂嫩戈本人则在卡洛斯的请求下，作为筑城工程师留在了西班牙。在圣塞瓦斯蒂安用堡垒防守要冲地点的形式建成西班牙第一座城塞的人就是他。这之后，他回到意大利，曾在帕维亚、热那亚、那不勒斯的城塞负责增建和修复工程。此外，他还长途跋涉前往荷兰的安特卫普，与另一名意大利工程师一道负责那里的城市防卫计划。
马尔蒂嫩戈在1544年死于威尼斯。直到去世的数年前，他都以为祖国没有原谅他擅自前往罗得岛。但是，这位威尼斯国籍的筑城工程师还在罗得城区向土耳其军开城前的1522年，留下了一封写给故乡弟弟的信函。信中表达了对不知威尼斯共和国如何看待自己擅自前往罗得岛的行为的担心，并详细叙述了攻防战中土耳其军的炮击和地雷。