Po upadku Akki w roku 1291, rycerze szpitalnicy przenieśli się na Cypr. Papież Mikołaj IV namówił joannitów oraz inne zakony rycerskie (m.in. templariuszy), aby zbudowali własne floty wojenne, w celu wykonania embarga na mameluckim Egipcie. W grudniu 1291 roku papież zażądał, aby połowa europejskich dochodów Zakonu została przeznaczona na budowę floty, a w styczniu 1292 roku upoważnił on Zakon do wykorzystania swoich nowych galer w celu obrony Ormiańskiego Królestwa Cylicji.
Pierwsza wzmianka o admirale floty Zakonu datuje się na rok 1299. W roku 1306 Zakon radykalnie przystosował się do walk na morzu i zaczął stawać się potęgą morską.
Rodos W roku 1309 Zakon odebrał Bizancjum wyspę Rodos i ustanowił tam swoją siedzibę. Od kiedy Zakon osiadł na wyspie, flota zaczęła być znaczącą częścią jego systemu obronnego.
W tym okresie Rycerze stoczyli kilka morskich bitew na Morzu Egejskim, jak np. w roku 1319, oraz wspomagali operacje morskie innych flot europejskich, jak np. na Eubei w roku 1344..
Malta thumb|Obraz ukazujący maltańskie galery zdobywające turecki statek w Cieśninie Maltańskiej w roku 1652.