Forgotten though fortunately well preserved, the Church of Santa Anastasia is a two-nave basilica with a transverse nave, located in Delimarkou St. at the "Kamaraki" on Kalokairinou Avenue. Mainly on account of its impressive construction, which is in line with the main principles of Gothic architecture, the church is unique among the town's monuments.

Santa Anastasia is attested in written sources as early as 1375 in the inventories of Chandax churches compiled by General Werdmüller and the geographer and traveller Coronelli, where it is referred to as the Chiesa Greca (Greek church).

Following the fall of Candia to the Turks, it was converted into a mosque dedicated to Recep Aga.