在同一时期，腓特烈还着手做了另外一件事，复兴罗杰二世死后一蹶不振的西西里王国的海军力量。
这时的腓特烈处于所有领域都在推行西西里王国中央集权化的高潮之中。在西西里，叙拉古是仅次于巴勒莫的重要城市，腓特烈不想承认这里的治外法权。在通商方面，如果同意外国势力自由行动，收益就是热那亚和比萨的，进不了西西里王国的国库。话虽如此，既然要把海上防卫交给他们，就不能把他们赶出居留区。
腓特烈把复兴王国海军的事业托付给了一位叫恩里克的人。我们只知道这个人是出生于马耳他岛的热那亚人。这人曾经做过海盗。腓特烈愉快地把打击海盗的事交给了海盗。可是没过多久，这位出生于马耳他岛的恩里克又当上了腓特烈的海军司令。在5年后开始的第六次十字军远征中，率领陆军的是正统德意志贵族、条顿骑士团的团长赫尔曼，而海军却交给了根本说不上出身正统的马耳他的恩里克。赫尔曼至死都坚守了对腓特烈的忠诚，而这位原来的海盗也把自己的一生奉献给了年龄小自己几岁的皇帝。在这点上这两人毫无二致。
西西里再大也还是个岛，海上安全保障重要无比。可是，腓特烈继承的海上防卫只能是依赖热那亚和比萨。然而，这两个海洋城邦国家是通商国家，它们把海外贸易作为主要的收入来源，不可能无偿让他们承包抵御来自北非的海盗袭击。他们要求并接受的“承包费”，是在位于西西里岛西南部自古以良港闻名的叙拉古各自拥有独立的居留区。
就这样，在海港城市叙拉古，靠近港口的一等地段一直以来都被热那亚和比萨的居留区所占据。就这两个国家的性质而言，居留区既是海军基地，同时又是通商基地。和当时地中海世界的其他居留区一样，叙拉古的居留区享有治外法权。
腓特烈要复兴西西里王国独自的海军力量，出发点就是要改善这种对王国经济不利的境况。他认为，为了能在自己合适的时候随时让他们撤出居留区，首先要完成海上防卫的自主化。这在祖父罗杰二世时代曾经做到过，半个世纪后的今天没有理由做不到。西西里岛的内陆地区也有丰富的木材资源可供造船使用。
5年以后，这样建起的西西里王国海军在腓特烈率领的第六次十字军行动中起到了重要的作用。而当初腓特烈着手复兴海军的意图其实在于实现海上防卫自主化。只要实现了这一点，就能阻止居住在西西里的萨拉森人和居住在北非的萨拉森人这两股伊斯兰势力联手。
