Λόγω της στρατηγικής του θέσης, η οποία επέτρεψε την πλήρη επίβλεψη της θάλασσας προς όλες τις κατευθύνσεις, και συνεπώς τις δραστηριότητες των πειρατών και των εχθρών, ο τόπος επιλέχθηκε από τους Ιππότες του Τάγματος του Αγίου Ιωάννη για την κατασκευή του κάστρου. Αρχικά, το κάστρο χωρίστηκε σε τρία επίπεδα, καθένα από τα οποία ανήκε και σε διαφορετικό Μεγάλο Μαγίστρο.
Το 1480, οι Οθωμανοί Τούρκοι έστειλαν 100.000 στρατιώτες στη Ρόδο σε μια προσπάθεια να εισβάλουν και να κατακτήσουν το νησί, με μεγάλο αριθμό στρατευμάτων να έχουν σταλθεί και στην Κρητηνία, προσπαθώντας να καταλάβουν το κάστρο. Ωστόσο, ανεξάρτητα από το γεγονός ότι οι Τούρκοι ξεπερνούσαν αριθμητικά τους Ιππότες, και μετά από πολλές αιματηρές μάχες, τα τουρκικά στρατεύματα τελικά υποχώρησαν, αφήνοντας το κάστρο γεμάτο ζημιές. Χωρίς να χάσουν χρόνο, οι Ιππότες αφοσιώθηκαν στην αποκατάσταση των ζημιών που είχε υποστεί το κάστρο, επαναφέροντας το στην αρχική του κατάσταση.
Σήμερα, μόνο το κέλυφος του κάστρου σώζεται ακόμα. Πάνω από είσοδο του, βρίσκονται τα οικόσημα δύο εκ των Μεγάλων Μαγίστρων της Μεσαιωνικής Εποχής: του Μεγάλου Μαγίστρου D'Amboise (1503-1512) και του Μεγάλου Μαγίστρου Origny (1467 - 1476). Μέσα στα τείχη υπάρχουν επίσης υπολείμματα ενός παρεκκλησίου αφιερωμένου στον Άγιο Ιωάννη, όπου μπορείτε να δείτε καταπληκτικές τοιχογραφίες του 16ου αιώνα.
Τοποθεσία κάστρου Κρητηνίας:
Το κάστρο βρίσκεται 48,6 χλμ. (Περίπου μία ώρα οδήγησης) από την πόλη της Ρόδου.