Ο σημερινός ναός της Κυρίας των Αγγέλων ή «Μικρή Παναγία», σε αντιπαραβολή με τη «Μεγάλη Παναγία», δηλαδή το μητροπολιτικό ναό του Ρεθύμνου, χτίστηκε τα τελευταία χρόνια της ενετοκρατίας και ήταν αφιερωμένη στην Αγία Μαρία Μαγδαληνή του τάγματος των Δομηνικανών.
Πρόκειται για μια τρίκλιτη εκκλησία που κατά την Τουρκοκρατία μετατράπηκε σε Τζαμί με μιναρέ.
Σύντομα, η κορυφή του μιναρέ έπεσε και από τότε ονομαζόταν «κουτσοτρούλης». Το 1917, μετατράπηκε σε ορθόδοξη εκκλησία. Κατά μια παράδοση οι χριστιανοί της πόλης σκηνοθέτησαν την εύρεση μιας εικόνας της Παναγίας, στα σκαλιά του μιναρέ (σήμερα βρίσκεται στο πρώτο δεξιά προσκυνητάρι της εκκλησίας) για να αναγκάσουν τους Τούρκους να τους παραχωρήσουν το ναό.