The first historical documents regarding Kostelzen appear in later 1344. In none of the Monastery documents from the Monastery in Kladrau between 1115 and 1239, mention Kostelzen. The story that the second of Bishop of Prague, the Holy Adalbert, during his return from Rome in 922 built a shrine to the Virgin Mary in Kostelzen, and housed his friend Anastasius there is a legend and should be regarded as such. In an official document from December 13, 1344 the Kladrau Monestary became the administrator of the Parish of Kostelzen. In recognition of the biannual papal tithes, in 1352 the church at Kostelzen paid 10 Groschens, and in 1399, 20 Groschens. The Kladrau Monastery belonged to the deanery of Horschau (Bischofteinitz). The most important historical document is in the church itself. In a an inscription in the wall next to the high alter, in a translation from the Latin, “In the year of our Lord 1356, the Choir of the was built by the parish priest Theodoricus. 1412, the parish priest of Kostelzen was named Inaugurator of the city of Kladrau. In the following time more and more parish officials were put into important positions within Kladrau. The abbot, Martin Lyra von Kladrau, began as a parish priest in Kladrau. During the aftermath of the closure of the Monastery in Kladrau in 1785, Kostelzen became one of 22 villages to break away from the grounds of the monastery. The church built in 1356 to celebrate the birth of St. John the Baptist, was restored in the Baroque style during the 18th century. During the 19th century, the portal of the church was bricked up, and a new tower was constructed. The record books kept in the church begin in 1645. The village sat 484 meters above sea level, and stood on exceptionally high ground. This meant that water was hard to procure, especially so in dry years. This lead to the people of Kostelzen being nicknamed the people of the snow, because of their high altitude. The people developed a system of irrigation, relying on two brooks that flowed from the Senetitzer Forest through Hammelhof and Alfredhof; a third flowed through the Lochutzner Dike of Radbusa. The historian Sommer reported in 1838, that the streams helped relieve droughts better than any in the dominion of Kladrau. The Volksschule was first described in 1838.