The church of Our Lady of the Castle is located at the eastern end of the Knights Street in Kollakio the Medieval City. The original core of the building was probably erected in the 11th century. and belonged to the type of cruciform domed temple. This architecture phase is evident to the genesis of some vaults.

According to the Ministry of Culture after the conquest of Rhodes by the Knights, the Byzantine church was reconstructed and took the form of three-aisled Gothic basilica with transept. The coats of arms of the Grand Master Helion de Villeneuve and Pope John XXII saved in the central pointed arch window militate in dating this phase between 1319 and 1334.

The east side of the church adjacent to the sea fortifications and shaped externally in rectangular tower with battlements. On the west side, above the main entrance door, saved a large rectangular frame, which would host painting composition, now lost, on the Virgin Mary with saints and knights.

During the Turkish occupation, the church was converted into a mosque and named Enteroum Mosque. At the same time built portico and minaret erected on the south side, construction elements which were removed during the reconstruction work carried out in the period of Italian occupation of the island.

From the church the painted decoration remains poorly maintained. It is worth mentioning the Virgin and Child and pairs of saints in the northwest pillar (vtetarto 14th c.) And the form of St. Lucia in the south wall, work probably Western European painter (second half 14th cent.).