Ο ναός του Παλαιοκήπου αποτελεί μία από τις ωραιότατες τρίκλιτες βασιλικές λεσβιακού τύπου που κοσμούν τις κοινότητες του νησιού. Φέρεται ότι στη θέση όπου βρίσκεται ο σημερινός υπήρχε παλαιότερος ναός, διότι αλλιώς δεν εξηγείται το πλήθος των αρχιτεκτονικών μελών που έχουν εντοιχισθεί στο σημερινό ναό. Κάτω από το δάπεδο του νοτίου κλίτους υπάρχει αψιδωτή καμάρα (κατακόμβη), η οποία αποτελούσε στο παρελθόν παρεκκλήσι επ’ ονόματι του αγ. Ιωάννου και αργότερα χρησιμοποιήθηκε σαν οστεοφυλάκιο, δεδομένου ότι ο νάρθηκας του ναού λειτούργησε ως χώρος ταφής μέχρι τα τέλη του 19ου αιώνα.
Η κτητορική επιγραφή δεν αναφέρεται σε ανοικοδόμηση ή ανακαίνιση, αλλά αναγράφει ότι ο ναός κτίστηκε εκ θεμελίων το 1795, χωρίς αυτό να αποκλείει την ύπαρξη προτέρου ναού. Η τοιχοποιία του κτιρίου είναι πολύ επιμελημένη, ιδιαιτέρως δε τριών αψίδων του ιερού βήματος και του νάρθηκα, που έχουν κτισθεί με ωραίους λαξευτούς λίθους χρώματος χρυσίζοντος κατά το ισόδομο σύστημα κι οι τοίχοι έχουν αρμολογηθεί σύμφωνα με το λεσβιακό σύστημα «Σαρδέλα». Το δάπεδο του ναού είναι μαρμαροστρωμένο από λευκό και φαιό μάρμαρο. Ο αρχιερατικός θρόνος και το παραθρόνιο στηρίζονται σε ωραία μαρμάρινα βάθρα. Τα τρία κλίτη του ναού χωρίζονται με σειρά από ψηλούς κίονες, οι οποίοι κοσμούνται από ωραία γύψινα κιονόκρανα κορινθιακού ρυθμού.
Το ξυλόγλυπτο τέμπλο του αν και δεν προέρχεται εκ της παλαιάς εποχής (17ου & 18ου αι.), μπορεί όμως να χαρακτηριστεί ως ένα απ’ τα ωραιότερα της εποχής του. Διατηρεί την παλαιά παράδοση της εκκλησιαστικής χειροτεχνίας και τη διαρθρωτική διάταξη και δομή των παλαιών τέμπλων. Η κατασκευή του πρέπει να τοποθετηθεί μεταξύ των ετών 1832-1841, σύμφωνα με τις χρονολογίες που υπάρχουν σε ανάγλυφες επ’ αυτού εικόνες. Της αυτής τεχνοτροπίας με το τέμπλο φυλάσσονται στο ναό και άλλα ξυλόγλυπτα σκεύη απαράμιλλης ομορφιάς, ήτοι αρχιερατικός θρόνος, φανοί, άμβωνας, αρτοφόριο, κουβούκλιο επιταφίου, καθώς επίσης και πολλές εικόνες χρονολογούμενες από των αρχών του 19ου αιώνος.
Ο ναός κοσμείται εξωτερικός και από ωραιότατο λίαν επιβλητικό κωδωνοστάσιο ύψους 17 μέτρων, κατασκευασμένο το 1900 από τον γνωστό πρακτικό αρχιτέκτονα Πέτρο Βέκιο.