Območje, ki ga je pozneje zasedla stolnica svetega Štefana, je ležalo vzhodno od rimskega legijskega taborišča Vindobona na območju canabae legiones, predmestja tabora. Tabor je bil od 1. do 3. stoletja obkrožen z zgradbami in ulicami, vendar so ga v 3. in 4. stoletju zamenjali grobovi in grobnice. Na območju Stock-im-Eisen-Platzes so bile od 1690 znova najdena grobišča.

Do srede 12. stoletja je Dunaj postal pomembno središče germanske civilizacije in štiri obstoječe cerkve, vključno z eno samo župnijsko cerkvijo, niso več zadovoljevale mestnih verskih potreb. Leta 1137 sta passavski škof Reginmar in mejni grof Leopold IV. podpisala Mauternsko pogodbo, ki je Dunaj prvič navedla kot civitas, pa tudi župnijske pravice, da je škofu omogočilo, da je zgradil zunaj takratnega mesta cerkev, posvečeno sv. Štefanu, zavetniku škofije v Passau. V skladu s pogodbo je mejni grof Leopold IV. od škofa dobil tudi razširjeno ozemlje čez mestno obzidje, z izjemo ozemlja, dodeljenega novi župnijski cerkvi, ki bo sčasoma postala stolnica svetega Štefana. Čeprav je prej veljalo, da je bila zgrajena na prostem pred mestnim obzidjem, je bila nova župnijska cerkev dejansko zgrajena na starodavnem pokopališču iz antičnih rimskih časov. Izkopi za ogrevalni sistem leta 2000 so razkrili grobove 2,5 metra pod površjem, ki so bili s karbonsko datacijo umeščeni v 4. stoletje. To odkritje kaže, da je bila na tem mestu še starejša verska zgradba kot cerkev sv. Ruperta, ki velja za najstarejšo cerkev na Dunaju.

 

Razvoj stolnice, ki prikazuje rimska stolpa in Velika vrata iz požgane prve cerkve (1137), drugo romansko cerkev (1263), gotski albertinski kor (1340) indodatki vojvode Rudolfa IV. (1359), ki je odstranil drugo cerkev in zgradil Stephansdom kot je videti danes.

Delno zgrajena romanska cerkev, ustanovljena leta 1137 po Mauternski pogodbi, je bila leta 1147 slovesno posvečena svetemu Štefanu v navzočnosti Konrada III. Nemškega, škofa Otisa iz Freisinga in drugih nemških plemičev, ki naj bi se podali na drugi križarski pohod.[1] Čeprav je bila prva konstrukcija dokončana leta 1160, so večje obnove in širitve trajale do leta 1511, projekti pa se s popravili in obnovami nadaljujejo do danes.

Od leta 1230 do 1245 se je prvotna romanska zgradba razširila proti zahodu; iz tega obdobja izhaja današnja zahodna stena in rimska stolpa. Leta 1258 pa je velik požar uničil velik del prvotne stavbe. Nad ruševinami stare cerkve so pod novim vladarjem Otokarjem II. Pšemislom postavili večjo nadomestno strukturo, prav tako romansko v slogu in ponovno uporabili oba stolpa ter jo posvetili 23. aprila 1263. [2] Obletnica tega drugega posvečenja vsako leto obeležujejo z redkim zvonjenjem Pummerinovega zvona tri minute zvečer. Leta 1276 je izbruhnil še en požar, ki je poškodoval kor, vendar ni vplival na zahodno pročelje in zahodno galerijo. Zahodno pročelje je še vedno ohranjeno in ga sestavljata dva Poganska stolpa in med njima Velika vrata. Poganska stolpa lahko izvirata iz kamnov, ki so prihajali iz starodavnih rimskih ruševin, morda iz dveh predstav nekrščanskih simbolov plodnosti falusa in vulve, ki kronata dva stebra zahodne stene pod stolpoma. Po legendi ime Velika vrata temelji na velikanski mamutovi kosti, obešeni nad vrati ali velikanu, ki je pomagal pri gradnji. Nad vrati je bila cesarska empora s stolom podobnim tistemu Karla Velikega v Aachnu.

Leta 1304 je kralj Albert I. vzhodno od cerkve naročil, da se vzpostavi gotski triladijski kor, ki bo dovolj širok, da zapolni stare transepte. Pod sinom, vojvodom [Albert II. Avstrijski|Albertom II.]] se je nadaljevalo delo na Albertinskem koru, ki je bil leta 1340 posvečen ob 77-letnici prejšnje posvetitve. Srednja ladja je v veliki meri posvečena sv. Štefanu in Vsem svetnikom, severna in južna ladja pa sta posvečeni sveti Mariji in apostolom. Vojvoda Rudolf IV., sin Alberta II., je znova razširil kor za povečanje dunajskega verskega vpliva. 7. aprila 1359 je Rudolf IV. postavil temelj za gotski prizidek Albertinskega kora na zahodu v bližini sedanjega južnega stolpa. Ta širitev bi sčasoma zajela celotno staro cerkev, leta 1430 pa je bila zgradba stare cerkve odstranjena od znotraj, ko so dela potekala na novi stolnici. Južni stolp je bil dokončan leta 1433, oboke ladje so delali od 1446 do 1474. Temelj severnega stolpa je bil postavljen leta 1450, gradnja pa se je začela z mojstrom Lorenzom Spenningom, vendar je bila njegova gradnja opuščena, ko so se večja dela na stolnici leta 1511 nehala.

 

Akvarel Jakoba Alta, 1847

Leta 1365, samo šest let po začetku gotskega prizidka Albertinskega kora, Rudolf IV. ni upošteval statusa svetega Štefana kot zgolj župnijske cerkve in domnevno ustanovil kapitelj kanonikov, ki ustreza veliki stolnici. Ta korak je bil le prvi korak pri izpolnitvi dolgotrajne želje Dunaja, da bi pridobil svojo škofijo; leta 1469 je cesar Friderik III. vplival na papeža Pavla II., da je Dunaju podelil svojo škofijo, škofa pa je imenoval cesar. Kljub dolgoletnemu odporu passavskih škofov, ki niso želeli izgubiti nadzora nad območjem, je bila dunajska škofija kanonično ustanovljena 18. januarja 1469, stolnica sv. Štefana pa je bila matična cerkev. Leta 1722, v času vladavine Karla VI., jo je papež Inocenc XIII. povzdignil v nadškofijo.[3]

Med drugo svetovno vojno se je stolnica rešila pred namernim uničenjem zaradi umika nemških sil, ko kapitan Wehrmachta Gerhard Klinkicht ni upošteval ukazov mestnega poveljnika "Seppa" Dietricha, da »izstrelijo sto granat in jo pustijo v ruševinah in pepelu.[4]« 12. aprila 1945 so civilni roparji podtaknili požare v bližnjih trgovinah, ko je sovjetska armada vstopila v mesto. Veter je ogenj zanesel v stolnico, kjer je močno poškodoval streho, zaradi česar se je zrušila. Na srečo so zaščitne opečne lupine, zgrajene okoli prižnice, grobnice Friderika III. in drugih zakladov, zmanjšale škodo na najdragocenejših umetninah. Vendar pa Rollingerjevih kornih klopi, izrezljanih leta 1487, ni bilo mogoče rešiti. Obnova se je začela takoj po vojni, z omejenim ponovnim odprtjem 12. decembra 1948 in popolnim ponovnim odpiranjem 23. aprila 1952.