Πολλές από τις ξεχασμένες ή χαμένες εκκλησίες του Χάνδακα σώζονται σήμερα τμηματικά, είτε μέσα σε σύγχρονα οικοδομήματα, είτε ως χαλάσματα. Ένα χαρακτηριστικό παράδειγμα είναι η "Κυρία των Αγγέλων", ο σημαντικότερος ορθόδοξος ναός της πόλης την περίοδο της Βενετοκρατίας. Ήταν έδρα του Πρωτόπαπα των Ορθοδόξων. Χτίστηκε το 13ο αιώνα στην αρχή της Πλατιάς Στράτας (Λεωφ. Καλοκαιρινού). Αναφέρεται στον πρώτο κατάλογο των εκκλησιών της πόλης, που συντάχτηκε από τον παπά κυρ Ιωάννη Κομητά, ως Santa Maria Degli Angelis in Beccharia (δηλ. Αγία Μαρία των Αγγέλων στα σφαγεία), επειδή πίσω από τον ναό υπήρχε η ομώνυμη συνοικία.
Την περίοδο της Τουρκοκρατίας ο ναός μετατράπηκε σε καφενείο. Ο Gerola μας πληροφορεί ότι ο ναός ήταν δίκλιτος με κατεστραμένο το νότιο κλίτος. Αναφορές σε έγγραφα του 1320 κάνουν λόγο για ένα ανοιχτό χώρο, ο οποίος υπήρχε έξω από το ναό και για ένα νεκροταφείο στα ανατολικά.
Σήμερα σώζεται το βόρειο κλίτος πλάτους 3,20 μ. μέσα στα καταστήματα που βρίσκονται στην αρχή της Λεωφ. Καλοκαιρινού.