By the middle of the 12th century, Vienna had become an important centre of German civilization, and the four existing churches, including only one parish church, no longer met the town's religious needs. In 1137, Bishop of Passau Reginmar and Margrave Leopold IV signed the Treaty of Mautern, which referred to Vienna as a civitas for the first time and transferred St. Peter's Church to the Diocese of Passau. Under the treaty, Margrave Leopold IV also received from the bishop extended stretches of land beyond the city walls, with the notable exception of the territory allocated for the new parish church, which would eventually become St. Stephen's Cathedral. Although previously believed built in an open field outside the city walls, the new parish church was in actuality likely built on an ancient cemetery dating to Ancient Roman times; excavations for a heating system in 2000 revealed graves 2.5 metres (8.2 ft) below the surface, which were carbon-dated to the 4th century.[citation needed] This discovery suggests that an even older religious building on this site predated the St. Rupert's Church, which is considered the oldest church in Vienna.

 Growth of the cathedral, showing the Roman towers and Giant's Door from the burned first church (1137), the Romanesque second church (1263), the Gothic Albertine Choir (1340), and the Duke Rudolf IV additions (1359), which removed the second church, leaving Stephansdom as it appears today.

Founded in 1137 following the Treaty of Mautern, the partially constructed Romanesque church was solemnly dedicated in 1147 to Saint Stephen in the presence of Conrad III of Germany, Bishop Otto of Freising, and other German nobles who were about to embark on the Second Crusade.[1] Although the first structure was completed in 1160,[2] major reconstruction and expansion lasted until 1511, and repair and restoration projects continue to the present day. From 1230 to 1245, the initial Romanesque structure was extended westward; the present-day west wall and Romanesque towers date from this period. In 1258, however, a great fire destroyed much of the original building, and a larger replacement structure, also Romanesque in style and reusing the two towers, was constructed over the ruins of the old church and consecrated 23 April 1263. The anniversary of this second consecration is commemorated each year by a rare ringing of the Pummerin bell for three minutes in the evening.

In 1304, King Albert I ordered a Gothic three-nave choir to be constructed east of the church, wide enough to meet the tips of the old transepts. Under his son Duke Albert II, work continued on the Albertine choir, which was consecrated in 1340 on the 77th anniversary of the previous consecration. The middle nave is largely dedicated to St. Stephen and All Saints, while the north and south nave, are dedicated to St. Mary and the Apostles respectively. Duke Rudolf IV, the Founder, Albert II's son, expanded the choir again to increase the religious clout of Vienna. On 7 April 1359, Rudolf IV laid the cornerstone for a westward Gothic extension of the Albertine choir in the vicinity of the present south tower. This expansion would eventually encapsulate the entirety of the old church, and in 1430, the edifice of the old church was removed from within as work progressed on the new cathedral. The south tower was completed in 1433, and vaulting of the nave took place from 1446 to 1474. The foundation for a north tower was laid in 1450, and construction began under master Lorenz Spenning, but its construction was abandoned when major work on the cathedral ceased in 1511.

 Watercolor by Jakob Alt, 1847

In 1365, just six years after beginning the Gothic extension of the Albertine choir, Rudolf IV disregarded St. Stephen's status as a mere parish church and presumptuously established a chapter of canons befitting a large cathedral. This move was only the first step in fulfilling Vienna's long-held desire to obtain its own diocese; in 1469, Emperor Frederick III prevailed upon Pope Paul II to grant Vienna its own bishop, to be appointed by the emperor. Despite long-standing resistance by the Bishops of Passau, who did not wish to lose control of the area, the Diocese of Vienna was canonically established on 18 January 1469, with St. Stephen's Cathedral as its mother church. In 1722 during the reign of Karl VI, Pope Innocent XIII elevated the see to an archbishopric.[2]

During World War II, the cathedral was saved from intentional destruction at the hands of retreating German forces when Wehrmacht Captain Gerhard Klinkicht disregarded orders from the city commandant, "Sepp" Dietrich, to "fire a hundred shells and reduce it to rubble".[3] On 12 April 1945, civilian looters lit fires in nearby shops as Soviet Army troops entered the city. The winds carried the fire to the cathedral, where it severely damaged the roof, causing it to collapse. Fortunately, protective brick shells built around the pulpit, Frederick III's tomb, and other treasures, minimized damage to the most valuable artworks. However, the Rollinger choir stalls, carved in 1487, could not be saved. Reconstruction began immediately after the war, with a limited reopening 12 December 1948 and a full reopening 23 April 1952.