Η Παναγία των Αγγέλων αναφέρεται στον πρώτο κατάλογο των εκκλησιών της πόλης του 1320 ως «Santa Maria degli Angelis in Beccharia (σφαγεία)». Μετά την κήρυξη του Αγίου Τίτου, έως τότε ορθόδοξου Μητροπολιτικού ναού, σε καθεδρικό των ενετών, η Παναγία των Αγγέλων αποτέλεσε έδρα του Πρωτόπαπα των Ορθοδόξων και σημαντικότερο ναό του ορθόδοξου πληθυσμού του Χάνδακα.

Στην οθωμανική περίοδο, ο ναός μετατράπηκε σε καφενείο με το όνομα «του Μπουργαρέζου ο Καβές», ενώ στον ίδιο χώρο, μέχρι το 1927-8, λειτουργούσε του Σαρχιανού Μιχάλη ο καφενές.

Βρίσκεται εκεί που τελειώνει η «Πλατειά Στράτα» (σημερινή λεωφόρος Καλοκαιρινού) και ενώνεται με την οδό Ίδης. Σήμερα οικοδομικά του λείψανα, σώζονται μέσα στα σύγχρονα καταστήματα της περιοχής.