Ο Άγιος Νικόλαος, στη συνοικία των Παλατιών, ανήκει στον αρχιτεκτονικό τύπο του σύνθετου σταυροειδούς εγγεγραμμένου με τρούλο ναού, με νάρθηκα δυτικά, του οποίου η οροφή έχει καταπέσει και περίβολο νότια και δυτικά. Χρονολογημένος στο 17ο αιώνα, είναι ο μοναδικός ναός μεγάλων διαστάσεων, που οικοδομήθηκε στο Μυστρά μετά την παράδοση της Καστροπολιτείας στους Τούρκους το 1460 και η λειτουργία του μαρτυρεί για την παραχώρηση προνομίων στους Έλληνες, όπως και την έντονη παρουσία τους στη γύρω περιοχή.

Ο ναός κτίστηκε με απλή λιθοδομή και μικρό αριθμό πλίνθων κατά τόπους, ενώ εσωτερικά ήταν κατάγραφος με τοιχογραφίες, από τις οποίες διατηρείται μικρό μόνο μέρος. Ολόσωμοι άγιοι, σκηνές από το Δωδεκάορτο και το Βίο του τιμώμενου αγίου Νικολάου διακρίνονται ακόμη, με καλύτερα σωζόμενες τον αρχάγγελο Γαβριήλ από τη σκηνή του Ευαγγελισμού στο βόρειο πεσσό μπροστά από το Ιερό, την Κοίμηση του αγίου Νικολάου στο κέντρο του βόρειου τοίχου και την εντυπωσιακή Δευτέρα Παρουσία ακριβώς απέναντι, στο νότιο τοίχο.

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