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

Το υπόλοιπο τμήμα του σημερινού ναού ανήκει στον 11^ο αιώνα.

Στο ναό σώζονται διάφορες τοιχογραφίες από τον 11^ο μέχρι και τον 14^ο αιώνα και μερικές αξιόλογες βυζαντινές εικόνες [όπως η μεγάλη εικόνα του αρχαγγέλου Μιχαήλ στο εικονοστάσι και του αγίου Ιωάννου του Θεολόγου (λυπητερό)].

Το περίφημο ψηφιδωτό του ναού, το οποίο παρουσιάζει την Παναγία με τον Χριστό ανάμεσα στους Αρχαγγέλους Μιχαήλ και Γαβριήλ, είναι από τα ελάχιστα της περιόδου αυτής (αρχές 7^ου αι.) που σώθηκαν σ’ όλο τον κόσμο. Αποτελεί, ακόμη, την παλαιότερη απεικόνιση της Θεοτόκου στην Κύπρο.

Η Θεοτόκος εικονίζεται όρθια στον εικονογραφικό τύπο της Οδηγήτριας, που πλαισιώνεται σύμφωνα με την αυτοκρατορική εθιμοτυπία από τους αρχαγγέλους Μιχαήλ και Γαβριήλ. Συνάμα, πρέπει να τονιστεί η επιγραφή η οποία αναφέρει «Η ΑΓΙΑ ΜΑΡΙΑ». Ο χαρακτηρισμός αυτός συνηθιζόταν πριν από τη Γ΄ Οικουμενική Σύνοδο της Εφέσου το 431, μετά την οποία επικράτησαν οι χαρακτηρισμοί Θεοτόκος ή Μήτηρ Θεού. Αυτή η ονομασία δεν πρέπει να θεωρηθεί μονοφυσιτική επίδραση, αλλά πιθανότερα αρχαϊκή επιβίωση χωρίς θεολογικές προεκτάσεις.

Τον 12^ο αιώνα προστέθηκε στη βόρεια πλευρά της εκκλησίας μικρό καμαροσκέπαστο παρεκκλήσι αφιερωμένο στους Αγίους Αναργύρους με τοιχογραφίες του 15^ου αι. και άλλες παλαιότερες. Κατά τον 14^ο αιώνα, κατά τη διάρκεια της Φραγκοκρατίας προστέθηκε στη νότια πλευρά λατινικό παρεκκλήσι, καλυμμένο με γοτθικά σταυροθόλια.

Η ονομασία «αγγελόκτιστη» οφείλεται στην παράδοση ότι κτίστηκε από τους αγγέλους. Ο R. Gunnis τη θεωρεί ως την ωραιότερη απ’ όλες τις εκκλησίες των χωριών της Κύπρου.