Ο ναός βρίσκεται στον εγκαταλελειμμένο οικισμό της Αράδαινας, σε απόκρημνο σημείο του φαραγγιού. Ιδρύθηκε τον 14ο αιώνα πάνω σε τρίκλιτη βασιλική του 6ου αιώνα, την περίοδο που η Αράδαινα αποτελούσε έδρα επισκοπής. Η αρχιτεκτονική του ναού δέχτηκε επιρροές από την Ελλαδική Σχολή, όπως φανερώνει ο ρυθμός του τετράστυλου σταυροειδή ναού με εξάπλευρο τρούλο. Μεταγενέστερες προσθήκες είναι το αρκοσόλιο με τον θολωτό τάφο της ενετικής περιόδου και ο νάρθηκας στα δυτικά, του 19ου αιώνα. Ο τοιχογραφικός διάκοσμος απεικονίζει επεισόδια από τον Χριστολογικό κύκλο, τον Αρχάγγελο Μιχαήλ, αγίους και τον βίο του αγίου Νικλάου. Οι τοιχογραφίες αντανακλούν τάσεις τοπικών εργαστηρίων του 14ου αιώνα, ενώ σώζεται επιγραφή με χαραγμένη τη χρονολογία 1546.