Confronted by the now firmly established Ottoman Sultanate, the Knights Hospitaller, whose headquarters were on the island of Rhodes, needed another stronghold on the mainland. Grand Master Philibert de Naillac (1396–1421) identified a suitable site across from the island of Kos, where a castle had already been built by the Order. Its location was the site of a fortification in Doric times (1110 BCE) as well as of a small Seljuk castle in the 11th century.

The construction of the castle began in 1404 under the supervision of the German knight architect Heinrich Schlegelholt. Construction workers were guaranteed a reservation in heaven by a Papal Decree of 1409. They used squared green volcanic stone, marble columns and reliefs from the nearby Mausoleum of Halicarnassus to fortify the castle.

The castle came under attack with the rise of the Ottoman Empire, first after the fall of Constantinople in 1453 and again in 1480 by Sultan Mehmed II. The attacks were repelled by the Knights of St John. When the Knights decided to fortify the castle in 1494, they used stones from the Mausoleum once again. The walls facing the mainland were thickened in order to withstand the increasing destructive power of cannon. The walls facing the sea were less thick, since the Order had little to fear from a sea attack due to their powerful naval fleet. Grand Master Fabrizio del Carretto (1513–21) built a round bastion to strengthen the land side of the fortress.

Despite their extensive fortifications, the Crusaders's towers were no match for the forces of Süleyman the Magnificent, who overpowered the knights in 1523. Under the Ottoman rule, the castle's importance waned, and in 1895 it was converted into a prison.