Um die Jahrhundertwende vom 12. zum 13. Jahrhundert wurde in Gnandstein – wohl etwa zeitgleich mit der Burg – eine erste Kirche erbaut. Von ihr sind im Innern noch heute romanische Putzreste unterhalb der Emporen zu erkennen. Auch das Radkreuz außen, unterhalb des Ostfensters ist diesem älteren Bau zuzuordnen. Der Neubau der spätgotischen Kirche wurde 1518 fertiggestellt. Heinrich von Einsiedel, der zum Zeitpunkt der Fertigstellung ihr Patronatsherr war, gehörte zu den frühen Anhängern der Wittenberger Reformatoren. Mit dem Neubau erhielt die Kirche ein Netzgewölbe mit Rippen aus rotem Porphyr und gotische Maßwerkfenster im Chor. Von Außen präsentiert sich der langgestreckte Bau mit einem steilen Satteldach. Im Norden wurde der Kirche eine Patronatsloge und der Treppenaufgang angefügt. Unterhalb der Patronatsloge kann man noch heute einen Blick in das Ossuarium, also das Beinhaus, des Friedhofes werfen. Im Innern wurde der Altar 1688 durch einen Kanzelaltar ersetzt. Er war damit einer der Ersten seiner Art in Sachsen. Ebenso ließen die Patronatherren ihre Loge prächtig mit den Wappen ihrer Verwandten schmücken und verdeutlichten so ihre Stellung im Land. Das Kirchenschiff unterscheidet sich von der herrschaftlichen Pracht. Nach der Vorlage der Bilderbibel des Matthaeus Merian d.Ä. schuf Tobias Pferts oder Perthes einen Zyklus, der das Leben Jesu von der Verkündigung bis zum Jüngsten Gericht in einem ländlichen barocken Stil zeigt.