Η εκκλησία της Παναγίας του Κάστρου βρίσκεται στο ανατολικό άκρο της οδού Ιπποτών, στο Κολλάκιο της Μεσαιωνικής Πόλης. Ο αρχικός πυρήνας του κτηρίου οικοδομήθηκε πιθανότατα κατά τον 11ο αι. και ανήκε στον τύπο του σταυροειδούς εγγεγραμμένου με τρούλο ναού. Η αρχιτεκτονική αυτή φάση αυτή είναι εμφανής έως τη γένεση περίπου των καμαρών.

Μετά την κατάληψη της Ρόδου από τους Ιωαννίτες ιππότες, η βυζαντινή εκκλησία μετασκευάστηκε και πήρε τη μορφή τρίκλιτης γοτθικής βασιλικής με εγκάρσιο κλίτος. Τα οικόσημα του μεγάλου μαγίστρου Helion de Villeneuve και του πάπα Ιωάννη XXII που σώζονται στο κεντρικό οξυκόρυφο παράθυρο της αψίδας συνηγορούν στη χρονολόγηση της φάσης αυτής μεταξύ των ετών 1319 και 1334.

Η ανατολική πλευρά του ναού εφάπτεται με την θαλασσινή οχύρωση και διαμορφώνεται εξωτερικά σε πύργο με ορθογώνιες επάλξεις. Στη δυτική όψη, επάνω από την κεντρική θύρα εισόδου, σώζεται ένα μεγάλων διαστάσεων ορθογώνιο πλαίσιο, το οποίο θα φιλοξενούσε ζωγραφική σύνθεση, χαμένη σήμερα, με θέμα την Παναγία με αγίους και ιππότες.

Κατά την περίοδο της Τουρκοκρατίας, ο ναός μετατράπηκε σε μουσουλμανικό τέμενος και ονομάστηκε Εντερούμ Τζαμί. Την ίδια εποχή κτίσθηκε στοά και υψώθηκε μιναρές στη νότια πλευρά, οικοδομικά στοιχεία τα οποία αφαιρέθηκαν κατά τις εργασίες αποκατάστασης του μνημείου που εκτελέστηκαν στην περίοδο της ιταλικής κατοχής του νησιού.

Από τον ζωγραφικό διάκοσμο της εκκλησίας διατηρούνται ελάχιστα λείψανα. Αξίζει να αναφερθεί η Παναγία Βρεφοκρατούσα και ζεύγη αγίων στο βορειοδυτικό πεσσό (β΄τέταρτο 14ου αι.) και η μορφή της αγίας Λουκίας στο νότιο τοίχο, έργο πιθανότατα δυτικοευρωπαίου ζωγράφου (β΄μισό 14ου αι.).