Κατά την περίοδο της τουρκοκρατίας, ο χώρος ανήκε σε κάποιον Τουρκορεθυμνιώτη, ο οποίος τον είχε μετατρέψει σε χαμάμ (δημόσιο λουτρό). Ξαφνικά, έπεσε στην πόλη μια θανατηφόρα αρρώστια η οποία χτυπούσε μόνο τις μωαμεθανικές οικογένειες, ενώ σι χριστιανοί επικαλούμενοι τη βοήθεια της Αγίας Βαρβάρας θεραπεύονταν. Οι Οθωμανοί για να γλιτώσουν από την ασθένεια, έπεισαν τον ομόθρησκό τους να αποδώσει το χώρο στους χριστιανούς για να ανεγερθεί ναός προς τιμήν της αγίας, όπως και έγινε. Ο ρυθμός του είναι σταυροειδής με τρούλο. Τον τρούλο του ναού αγιογράφησε ο εξηντάρης τότε, Επίσκοπος Ιερόθεος Μπραουδάκης, αφού πρώτα νήστεψε δύο εβδομάδες. Από το 1898 μέχρι το 1907, είχε παραχωρηθεί στις ρωσικές δυνάμεις κατοχής για την εκτέλεση των θρησκευτικών τους καθηκόντων.