Η εκκλησία σώζεται στην οδό Δελημάρκου, στο «Καμαράκι», μεταξύ της λεωφόρου Καλοκαιρινού και της οδού Ντεντιδάκηδων. Διατηρημένη, σε πολύ καλή κατάσταση, αποτελεί ένα μοναδικό μνημείο της πόλης, κυρίως λόγω της εντυπωσιακής κατασκευής της που ακολουθεί τις βασικές αρχές του γοτθικού ρυθμού.
Η Αγία Αναστασία αναφέρεται στις γραπτές πηγές από το 1375. Στους καταλόγους VI (Werdmüller) 105 και VII (Coronelli) 66 αναφέρεται ως S. Anastasia και Santa Anastasia, Chiesa Greca αντίστοιχα.
Ο ναός ανήκει στον αρχιτεκτονικό τύπο της δίκλιτης βασιλικής με εγκάρσιο κλίτος και έχει ορθογώνια κάτοψη, με γοτθικά οξυκόρυφα τόξα που χωρίζουν τα δύο κλίτη και ισχυρές αντηρίδες που στηρίζουν την τοιχοδομία εξωτερικά. Σπάνιο για τους ναούς του Χάνδακα είναι το εγκάρσιο κλίτος στην ανατολική πλευρά, με ελαφρά απόκλιση από την κάθετο των άλλων δύο. Δύο ακόμα οξυκόρυφα τόξα συνδέουν το κάθετο κλίτος με τα δύο κεντρικά. Τα μεγάλα οξυκόρυφα παράθυρα αποτελούν βασικά χαρακτηριστικά του οικοδομήματος.
Ο Gerola την περιέγραψε ως εξής: Δύο γοτθικά οξυκόρυφα τόξα πάνω σε κίονες εξασφαλίζουν την επικοινωνία μεταξύ των δύο κλιτών κατά μήκος του άξονά τους και άλλα δύο με το εγκάρσιο κλίτος. Οι καμάρες της πρόσοψης έχουν δύο τόξα. Οι πόρτες και τα παράθυρα είναι νέες κατασκευές. Εξωτερικά σώζονται αντηρίδες.
Μετά την άλωση του Χάνδακα από τους Οθωμανούς, μετατράπηκε στο τέμενος Retzep Agha.
Η εκκλησία της Αγίας Αναστασίας, μετά την απελευθέρωση της Κρήτης, κατέστη ανταλλάξιμο κτήμα με αρ. 2744. Το 1924 πουλήθηκε από την Εθνική Τράπεζα στον μηχανικό Ιωσήφ Χατζηδάκη και μετατράπηκε σε καταστήματα και αποθήκες.
Κηρύχθηκε ιστορικό διατηρητέο μνημείο με το ΠΔ της 18/3/1947.
Σήμερα στεγάζει κατάστημα επίπλων.
