Vienna was rather a late starter among medieval cities, not much of a place until the twelfth century. Until then it was confined within the walls of an old Roman frontier fortress, Vindobona. But as trade along the Danube grew and the city's political importance increased it burst those bounds, and the walls had to be extended to take in the growing settlement. Vienna was not then a cathedral city, but the wealthy merchants who controlled it wanted a great church that would give physical expression to the faith and money. So in 1137 they began building a major new church in the Romanesque style. You can still see the facade of this church, incorporated into the west front of the later cathedral. The towers are called the Heidentürme or "pagan towers," I suppose to indicate how ancient they are.
There are also still numerous bits of Romanesque sculpture in various nooks and crannies.
The main entrance is known as the Riesentor or Giant's Door. Depending on what you read, this might be because of its size, or because the thighbone of a mastodon hung over it for decades after turning up in 1443 during the excavation of the foundations for the north tower. The old church was damaged by fire in the mid thirteenth century, and it was reconstructed larger than before. The fabric of that church was almost entirely removed during the fourteenth-century enlargement.
In the fourteenth century, as the town grew ever larger and the Dukes of Austria ever more important, The church was greatly enlarged and transformed into a gothic masterwork. The expansion began in 1304 and was not completed until 1459.
The great south tower was completed in 1433.
In 1469 the Pope agreed to make Vienna a bishopric, so the church became a cathedral at last.
The church was badly damaged by a fire in April, 1945. The date is usually given as Friday, April 13, but wikipedia insists on April 12. (Spoilsports!) The fire was caused by looting of shops in the central city, not allied bombs.
The roof had to be completely rebuilt. Steel beams were used rather than wood, and the famous roof tiles were all replaced with new ones bought by Vienna's citizens.
The most important interior sculptures had been removed or bricked in before the fire, so they survived the disaster.
The pulpit, completed in 1515, is a particular wonder. I thought that this was attributed to Anton Pilgram, but wikipedia says that now opinion has shifted and more experts think the carving was done by Pilgram's teacher, Niclaes Gerhaert van Leyden. Those are the Doctors of the Church, looking delightfully cartoonish.
The Viennese, as you will discover if you ever visit, are not much into scenic ruins. Vienna is the neatest, cleanest big city I have ever been in, with the best maintained buildings and the best-dressed people. So of course they are not much interested in a crumbling cathedral. Some part of the building has been under restoration since World War II, and that includes all of the altars, sculptures, and so on. No noseless saints here. I like it this way.