
Hrad postavil mistr Giorgio Orsini da Sebenico roku 1472 nad vesnicí Kritinia založenou uprchlíky z Kréty, kteří sem uprchli před tureckou okupací. Z důvodu nebezpečí útoku pirátů byla však později vesnice přesunuta 2 km do vnitrozemí. Až do osvobození souostroví Dodekanésos se nazývala Kastellos podle latinského "castellum", což znamená pevnost. Dnes je většina zbytků původní osady zaplavena a zůstaly z ní jen trosky kostela. V roce 1480 se osmanské vojsko s velkou početní převahou pokoušelo hrad několikrát dobýt, vždy však bez úspěchu. Johanité jej poté znovu opravili. V roce 1658 se Francesco Morosini z Benátek pokusil dobýt Rhodos vyloděním na pláži Kamiros, ale jeho vojsko bylo odraženo. V průběhu staletí byl hrad několikrát přestavěn. Během italské okupace byl hrad využíván jako námořní základna a proto je nejzachovalejším hradem na Rhodosu.
Podle pověsti měl nejstarší syn Katerase a vnuk Mínóse (krétského krále) Athaimeles opustit svou rodnou zem poté, co mu bylo vyřčeno kruté proroctví, podle něhož měl Athaimeles zabít svého vlastního otce. Po opuštění rodných břehů měl přistát na ostrově Rhodos a založit zde Kritinii.