Το σπουδαιότερο ορθόδοξο μοναστήρι στο Χάνδακα ήταν εκείνο της Αγίας Αικατερίνης των Σιναϊτών. Η ύπαρξη στο Χάνδακα μονής αφιερωμένης στην Αγία Αικατερίνη μνημονεύεται από τη β΄ βυζαντινή περίοδο, όμως μέχρι στιγμής δεν έχουν εντοπιστεί ίχνη της. Το σωζόμενο κτήριο αποτελούσε το καθολικό κατά το 16ο αιώνα. Είναι δρομικός καμαροσκέπαστος ναός με εγκάρσιο κλίτος, που διαμορφώνεται με χαμηλότερα στεγασμένα πτερά, ενώ το ιερό Βήμα πλαισιωνόταν από δυο μικρούς ορθογώνιους χώρους, που πρέπει να λειτουργούσαν ως παραβήματα. Σήμερα το νότιο παράβημα έχει καταρρεύσει και μόνο ίχνη των ανοιγμάτων επικοινωνίας καθώς και το περίγραμμα της εξωτερικής του τοιχοποιίας διατηρείται σε χαμηλή στάθμη εξωτερικά του μνημείου. Παλαιότερα είχε αξιοποιηθεί ως δεξαμενή. Το ιερό, τα παραβήματα και τα πτερά του εγκαρσίου κλίτους στεγάζονται με οξυκόρυφη καμάρα ενώ το κυρίως κλίτος με ημικυλινδρική. Ημικυκλικά τόξα διαμορφώνουν τα ανοίγματα επικοινωνίας του ιερού με τα παραβήματα και οξυκόρυφα τα ανοίγματα επικοινωνίας των παραβημάτων με τα πτερά του εγκαρσίου κλίτους.

Στη βόρεια πλευρά του εγκαρσίου κλίτους προσκολλάται παρεκκλήσιο αφιερωμένο σήμερα στους Αγίους Δέκα. Αποτελείται από δυο διαδοχικούς περίπου τετράγωνους χώρους, από τους οποίους ο δυτικός στεγάζεται με σταυροθόλιο και ο ανατολικός με τρούλο που στηρίζεται σε γωνιακά ημιχώνια, τονίζεται εσωτερικά με λίθινες νευρώσεις και απολήγει σε φανό.

Στο βόρειο τοίχο του δυτικού χώρου του παρεκκλησίου των Αγίων Δέκα σώζεται οξυκόρυφο γοτθικό παράθυρο, εμφραγμένο στο κάτω τμήμα του λόγω υπερύψωσης της στάθμης του δαπέδου. Η μορφή του είναι αντίστοιχη με τα παράθυρα του φωταγωγού της βασιλικής του Αγίου Μάρκου και του ναού του Αγίου Πέτρου των Δομηνικανών. Το στοιχείο αυτό υποδεικνύει ότι η αρχική κατασκευαστική φάση του μνημείου ανάγεται πιθανότατα στο 13^ο ή 14^ο αιώνα. Στην αρχική οικοδομική φάση πρέπει να αποδοθεί και το ανατολικό τμήμα του κυρίως ναού έως και το εγκάρσιο κλίτος. Έτσι ο κυρίως ναός, με τα χαμηλότερα στεγασμένα πτερά του εγκαρσίου κλίτους και τα παραβήματα που πλαισίωναν το ιερό, φαίνεται ότι ακολουθούσε σε γενικές γραμμές τον αρχιτεκτονικό τύπο του Αγίου Πέτρου των Δομηνικανών. Στη διάρκεια του 16^ο αιώνα το μνημείο γνώρισε εκτεταμένη επισκευή. Το τμήμα δυτικά του εγκαρσίου κλίτους ανακατασκευάστηκε, όπως μαρτυρούν το διαφορετικό διαχωριστικό γείσο στη γένεση του θόλου, ο πολυτελής διάκοσμος στους κιλίβαντες των δυο ανατολικών σφενδονίων του και η μορφή των παραθύρων, που έχουν ημικυκλική άνω απόληξη και επιστέφονται από μεγάλους κυκλικούς οφθαλμούς. Την ίδια εποχή προστέθηκε ο τετράγωνος ανατολικός χώρος του παρεκκλησίου των Αγίων Δέκα, ο οποίος κοσμήθηκε με αναγεννησιακού τύπου τρούλο με νευρώσεις που καταλήγουν στη βάση τους σε σταγόνες με πλούσιο ανάγλυφο φυτικό διάκοσμο αντίστοιχου ύφους με εκείνο των υφαψιδίων του κυρίως ναού. Στη διάρκεια της επέμβασης τοποθετήθηκε επίσης το αναγεννησιακού τύπου θύρωμα της δυτικής όψης του κυρίως ναού, το οποίο φαίνεται ότι διέθετε αετωματικού τύπου απόληξη που δε σώθηκε, είχε όμως αφήσει ίχνος στην τοιχοποιία πίσω της, καθώς και ολόκληρη η αετωματική πρόσοψη του παρεκκλησίου.

Αμέσως μετά την κατάληψη της πόλης από τους Οθωμανούς η Αγία Αικατερίνη μετατράπηκε σε τζαμί, γνωστό με το όνομα Ζουλφιακάρ Αλή πασά ή Αγιά Κατερίνα Τζαμισί, που λειτούργησε το 1922. Μπροστά από τη νότια παραστάδα της πρόσοψης του παρεκκλησίου προστέθηκε μιναρές, που κατεδαφίστηκε μετά τη εγκατάλειψη του τζαμιού και διατηρεί σήμερα μόνο τη βάση με τμήμα της κλίμακας ορατό από το εσωτερικό. Από τα προσαρτήματα της μονής δεν διασώθηκε τίποτε. Μετά την απελευθέρωση το καθολικό αποτέλεσε για ένα διάστημα σιταποθήκη και προσωρινό κατάλυμα των Μικρασιατών προσφύγων. Αγοράστηκε τελικά ως ανταλλάξιμο κτήμα από την ενορία του Αγίου Μηνά και χρησιμοποιήθηκε για λατρευτική χρήση από το 1944 ως το 1967, οπότε αποφασίστηκε η λειτουργία του ως χώρου έκθεσης της συλλογής κειμηλίων της Ιεράς Αρχιεπισκοπής Κρήτης. Σήμερα στεγάζει την ανακαινισμένη έκθεση της συλλογής, έργο που υλοποιήθηκε από τη 13^η Εφορεία Βυζαντινών Αρχαιοτήτων με χρηματοδότηση του Ε.Π. Κρήτης και Νήσων Αιγαίου του ΕΣΠΑ 2007-2013 (www.iakm.gr).