It is a three aisled church, whose central aisle ends in a three-sided apse. The frescoes that decorate the central aisle are of the late 14th century and those of the side-aisles are of the late 15th. The murals of the south aisle contain the iconographic cycle of St. Catherine.
The monument was turned into a mosque during the Ottoman occupation of Rhodes (1522-1912). According to tradition, Suleiman The Magnificent prayed there when he conquered the town.
In 1981, excavation inside the church revealed graves under the north aisle: arcosolia and simple burials. In 1992, excavation of the south aisle produced similar results.