The first stone was laid on 1 May 1862—an event solemnised by the performance of Anton Bruckner's Festive Cantata Preiset den Herrn.

The plans, drawn by the master builder of the Archdiocese of Cologne, Vincenz Statz, were made in the French high Gothic style.

The originally-planned, higher spire was not approved, because in Austria-Hungary at the time, no building was allowed to be taller than the South Tower of the St. Stephen's Cathedral in Vienna.

In October 2006 the Catholic Church added a plaquet to the commemorative wood cut for Engelbert Dollfuß at the New Cathedral, which caused excitement in the ÖVP.

In the plaque the church, by resolution of the Austrian Conference of Catholic Bishops, distances itself from the original cut and proclaims the future abstention from party politics.