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