The Protestant church acquired a plot of land at the outlying village of Matzleinsdorf that same year and began the construction of their first cemetery in Vienna.

Superintendent of the Calvinist H.B (Evangelische Kirche Helvetisches Bekenntnis) Gottfried Franz gave the blessing speech, while the Lutheran A.B (Evangelische Kirche Augsburger Bekenntnis) Superintendent Ernst Pauer performed the consecration of the burial ground, and on September 27, 1860 the chapel Christuskirche (Chapel of the Holy Christ) was completed and consecrated.

The architect, Theophil Hansen, was influenced heavily by historical features prominent during the 19th century and constructed the church in a Byzantium style with a large dome and crowned corner pillars.

The ornate stained glass windows are ornamented with Christian symbols, depicting the nativity, crucifixion and resurrection of the Christ.

During its long history, the Matzleinsdorf cemetery became so popular among the Viennese Protestants that it needed to be enlarged twice due to a lack of space.