Ο ναός των Αγίων Κηρύκου και Ιουλίττας οικοδομήθηκε το 14ο αιώνα από τον επίσκοπο Μακάριο, σύμφωνα με την κεραμοπλαστική επιγραφή που βρίσκεται στην εξωτερική πλευρά της κόγχης του ιερού. Όπως μας πληροφορεί επιστολή του Πατριάρχη Αντωνίου Δ΄, που χρονολογείται στο 1395, ο ναός υπήρξε καθολικό μονής και αργότερα, άγνωστο πότε, εξέπεσε από μονύδριο και μετατράπηκε σε ενοριακό ναό. Αυτό οπωσδήποτε συνέβη πριν από το 1589, όταν ο άρχοντας κυρ Κωστής προσέφερε χορηγία για τη νέα αγιογράφηση του ναού.

Ο αρχικός ναός ανήκε στον τύπο του σταυροειδούς εγγεγραμμένου με τρούλο. Αργότερα, πιθανόν τον 16ο αιώνα, ο τρούλος κατέρρευσε και ο ναός προσέλαβε τη μορφή μονόχωρου ξυλόστεγου πυρήνα, γύρω από τον οποίο, σε άγνωστη εποχή, κατασκευάσθηκε περίστωο. Ιδιαίτερο ενδιαφέρον παρουσιάζει η ανατολική εξωτερική όψη του μνημείου, η οποία σώζει πλούσιο κεραμοπλαστικό διάκοσμο στις τρεις αψίδες. Από τον τοιχογραφικό διάκοσμο διατηρούνται υπολείμματα των μέσων του 14ου αιώνα στο χώρο της πρόθεσης, και του 15ου αιώνα στον εξωτερικό δυτικό και στο νότιο τοίχο του κεντρικού πυρήνα του ναού. Σύμφωνα με την επιγραφή που βρίσκεται πάνω από τη θύρα της δυτικής εισόδου, το έτος 1589 ο άρχοντας κυρ Κωστής ανέλαβε την εκ νέου αγιογράφηση του μνημείου. Τότε τοιχογραφήθηκε η κόγχη του ιερού βήματος, ο βόρειος και ο νότιος τοίχος του ιερού, και η πρόθεση. Στην ίδια περίοδο ανήκουν και οι τοιχογραφίες του κυρίως ναού, οι οποίες διατάσσονται σε τρεις ζώνες. Η χαμηλότερη περιλαμβάνει ολόσωμους αγίους, η δεύτερη σκηνές από το βίο του Προφήτη Ηλία, καθώς και άλλα θέματα, όπως η Προσευχή του Ιωακείμ, ο Ευαγγελισμός της Άννας, ο Ασπασμός του Ιωακείμ και της Άννας, και ο άγιος Ιγνάτιος υπό λεόντων, και τέλος, η τρίτη ανώτερη ζώνη σκηνές Δωδεκαόρτου. Το 17ο αιώνα φράχθηκαν τα ανοίγματα του τέμπλου, και στις όψεις προς τον κυρίως ναό παραστήθηκαν ένθρονοι ο Χριστός και η Παναγία.