בעבר רווחה הסברה שהכנסייה נבנתה בשדה פתוח מחוץ לחומות העיר; אך חפירות שנערכו בשנת 2000, במטרה להתקין מערכת חימום, חשפו קברים שתוארכו באמצעות פחמן רדיואקטיבי למאה ה-4, בעומק 2.5 מטר מתחת לפני הקרקע. 430 השלדים שנמצאו שם הועברו לקטקומבות. הועלו סברות כי ייתכן שאלפים אחרים נקברו בבית קברות עתיק זה, החל מהתקופה הרומית, וכי כנסייה זו, ולא כנסיית רופרכט (Ruprechtskirche), היא הכנסייה העתיקה ביותר בווינה.
הכנסייה המתועדת הראשונה באתר נבנתה ב-1137 בידי הדוכס לאופולד הרביעי תחת חוזה מאוטרן עם רגינמאר הבישוף של פאסאו. הכנסייה הוקדשה לסטפנוס הקדוש, הפטרון של קתדרלת הבישוף בפאסאו. המבנה הראשון נבנה בסגנון רומנסקי, ונחנך עשר שנים לאחר מכן במעמד קונראד השלישי, מלך גרמניה, הבישוף אוטו מפרייזינג ועוד מספר רב של אצילים שעמדו לצאת למסע הצלב השני. ברם, הוא הושלם רק ב-1160, ומאז עבר סדרת שינויים ושיפוצים. הקיר המערבי הנוכחי וצמד המגדלים הרומאניים מתוארכים ל-1237. בשנת 1258 פרצה שרפה גדולה בעיר, שכילתה גם את הכנסייה. במקומה נבנתה כנסייה שנייה, גדולה יותר, גם היא בסגנון רומנסקי, ששילבה את המגדלים הרומים והשער, ונחנכה ב-23 באפריל 1263, תאריך שמצוין כל שנה על ידי צלצול הפעמון הגדול (פומרין) במשך כשלוש דקות. מבנה זה היה הכנסייה השנייה באתר.
בשנת 1304 הורה הקיסר אלברכט הראשון על בנייה של בית מקהלה בן שלושה אגפים בסגנון גותי ממזרח לכנסייה, באופן שיהיה רחב דיו לפגוש את קצוות בית הרוחב הישן. העבודה נמשכה תחת שלטון בנו, הדוכס אלברכט השני; בית המקהלה החדש נחנך ב-1340, ביום השנה ה-77 לחנוכת הכנסייה הקודמת. המוטיב של הריהוט באגף הצפוני עסק במריה הקדושה, באגף המרכזי בסטפנוס הקדוש ובשאר הקדושים, ובאגף הדרומי בשנים-עשר השליחים. חלק זה של הקתדרלה הנוכחית נמצא מזרחית לבית הרוחב הקצר והעבה, ונקרא "בית המקהלה האלברטיני".
ב-1359 הניח בנו של אלברכט השני, רודולף הרביעי, דוכס אוסטריה "המייסד", את אבן הפינה באזור המגדל הדרומי להרחבה של הכנסייה מערבה בסגנון גותי, הרחבה שמקיפה את הכנסייה הישנה. לאחר השלמת המבנה הגותי פורקה הכנסייה הישנה והוצאה מתוך המבנה. רודולף הרביעי העלה את מעמד הכנסייה ומינה מועצת קנונים הראויה לקתדרלה.
ואכן, בשנת 1469, בעקבות בקשתו של פרידריך השלישי, קיסר האימפריה הרומית הקדושה, העניק האפיפיור פאולוס השני מעמד של דיוקסיה לווינה ובעקבות זאת מינה הקיסר בישוף לכנסיית סטפנוס הקדוש, שנהפכה לקתדרלה. הדיוקסיה נחנכה ב-18 בינואר 1469 כאשר קתדרלת סטפנוס הקדוש היא מרכזה. ב-1722 תחת שלטונו של קרל החמישי, קיסר האימפריה הרומית הקדושה, העלה האפיפיור אינוקנטיוס השלושה עשר את הבישופות לדרגה של ארכיבישופות.
קתדרלת סטפנוס הקדוש ניצלה מנזק מכוון בידי הוורמאכט הגרמני בזמן מלחמת העולם השנייה, כאשר סרן גרהרד קלינקיכט התעלם מפקודות של מפקד העיר זפ דיטריך "לירות מאות פגזים ולהשאיר אותה בהריסות ואפר".
ב-12 באפריל 1945 נפגעה הקתדרלה קשות מאחת השריפות, שהוצתה בידי בוזזים כאשר חיילים רוסיים נכנסו לעיר. מגן מלבנים נבנה סביב דוכן הדרשה, קברו של פרידריך השלישי ואוצרות אחרים, כך שהנזק לאוצרות האמנות היקרים ביותר היה מזערי. עם זאת, השרפה כילתה את ספסלי המקהלה שגולפו בעץ על ידי וילהלם רולינגר בין השנים 1476 ו-1487 שיקום המבנה החל מיד לאחר תום המלחמה, והוא נפתח חלקית ב-12 בדצמבר 1948 ובאופן מלא ב-23 באפריל 1952.
חוץ המבנה.
אורך הקתדרלה הרומנסקית-גותית הוא 107 מטר, ורוחבה 34 מטר. הפיח שהצטבר עליה במשך השנים ופגע בחזותה נוקה בשנים האחרונות, וכעת חזית הכנסייה שוב בגוון המקורי.
ה"שטפל" - המגדל הדרומי.
המגדל הדרומי המסיבי והגבוה של קתדרלת סטפנוס הקדוש (ראו בתוכנית המבנה: ST) הוא המאפיין הבולט של קו הרקיע של וינה. הצריח המחודד הגותי שבראשו מתנשא לגובה של כ-136.7 מטר ומכונה בחיבה שטֶפל (Steffl); לשון הקטנה של "סטפנוס" בגרמנית) בפי הווינאים. הוא שימש כנקודת התצפית והפיקוד העיקרית בהגנת העיר מוקפת החומות בעת המצור על וינה ב-1523 ובמצור השני ב-1683. זהו הסמל המוכר ביותר של וינה. נדרשו 65 שנה להשלימו, מ-1368 עד 1433. המגדל מכיל דירה לשומר, שבמשך מאות שנים (עד 1955) אייש את המגדל בלילות וצלצל בפעמון אם איתר שרפה. קצה המגדל נושא את החותם הקיסרי, עיט כפול עם סמל הגיבורים של בית הבסבורג-לוריין (השושלת שהמשיכה את בית הבסבורג) על חזהו ובנוסף צלב אפוסטלי בעל שתי זרועות המסמל את הסגנון "מלכותיות אפוסטולית" של הקיסרים ההאבסבורגיים כמלכי הונגריה.
המגדל הצפוני.
המגדל הצפוני (ראו בתוכנית המבנה: NT) תוכנן להיבנות כתאום למגדל הדרומי, אך מעולם לא הושלם. גובהו הוא רק כמחצית מאחיו הדרומי, 68 מטר. בקצהו כיפה זמנית, אותה מכנים הווינאים "גג מגדל המים". בנייתה הופסקה ב-1511 ומאז לא הושלמה.
החזית המערבית.
הכניסה הראשית נקראת "שער הענק" ("ריזנטור" או "Riesentor") בשל עצם של מסטודון שהייתה תלויה מעליה בעבר. משמאלה ומימינה נמצאים המגדלים הרומים (ראו בתוכנית המבנה: RT). גובה כל אחד מהמגדלים 65 מטר. הם נקראים "רומים" ("heidnischen" בניב וינאי) מכיוון שנבנו מחורבות מבנים רומיים. בסיסם רבוע, שעם עלייתו מעל לגג הופך למתומן. המגדלים הרומים (Heidentürme) מכילים פעמונים, ואף שהמגדל הרומי הדרומי איבד את פעמוניו בזמן מלחמת העולם השנייה, פעמוניו של המגדל הצפוני עדיין פעילים ביחד עם "דלת הענק", הם החלקים העתיקים ביותר בכנסייה. הטימפנון מעל הכניסה מתאר את "ישו המלך", ומשני אגפיו מלאכים מכונפים.
הגג.
קתדרלת סטפנוס הקדוש ידועה בזכות הגג המקושט והצבעוני שלה, שאורכו 110 מטר והוא מכוסה ב-230,000 רעפים מזוגגים. מעל לבית המקהלה, על צד אחד של המבנה ישנם רעפים היוצרים פסיפס של העיט הדו-ראשי המסמל את קיסרות בית האבסבורג ששלט בווינה, ובצד השני מופיעים שלט האצולה של העיר וינה והרפובליקה של אוסטריה. ב-1945, כחלק מנזקי מלחמת העולם השנייה, התפשטה שרפה מן הבניינים הסמוכים אל המגדל הצפוני של קתדרלת סטפנוס הקדוש, והרסה את הגג. שחזור חישוקי העץ המקוריים לגג כה גדול (המתנשא לגובה 38 מטרים מעל לקירות) היה דורש קילומטר רבוע של יער, ולכן 600 טון של חישוקי פלדה הותקנו במקומם. הגג הוא תלול מאוד (שיפוע של מעל 80 מעלות במקומות אחדים), כך שירידת גשם מספיקה כדי לנקותו, ולעולם לא נערם עליו שלג.
פעמונים.
בקתדרלת סטפנוס הקדוש יש 23 פעמונים.
הפעמון הגדול ביותר נקרא על שם מריה הקדושה, אך מכונה בפי כל "פומרין" (בתרגום חופשי: "המרעימה"). פעמון זה תלוי במגדל הצפוני ושוקל כ-20 טון. זהו הפעמון הגדול ביותר באוסטריה, ופעמון הנדנוד השני בגודלו באירופה (אחרי פעמון "פטר" בקתדרלת קלן השוקל כ-23 טון). הפעמון נוצק במקור בשנת 1711 מתותחים שנלכדו מהפולשים המוסלמים, ונוצק מחדש (בחלקו מהמתכת המקורית) ב-1951 לאחר שנפל והתרסק בשנת 1945 כתוצאת משרפתה של מסגרת העץ שהחזיקה אותו. הפעמון החדש הוא בקוטר 3.14 מטר (קרוב מאוד לערכו של פאי), וניתן במתנה ממדינת אוסטריה עילית. הוא מצלצל רק במספר אירועים מיוחדים כל שנה, כולל ביום השנה החדשה. ישנם עוד שלושה פעמונים אחרים במגדל הצפוני, אך הם ישנים יותר ויצאו מכלל שימוש.
במגדל הדרומי מותקנים אחד עשר פעמונים המופעלים חשמלית, שנוצקו ב-1960. הם החליפו פעמונים ישנים יותר שנהרסו בשרפה של 1945, ומצלצלים בזמן מיסות בקתדרלה: ארבעה מהם מצלצלים במיסה רגילה, עשרה פעמונים מצלצלים במיסה של חג חשוב, והפעמון ה-11 והגדול ביותר נוסף כאשר הקרדינל והארכיבישוף של וינה נוכח. מהגדול ביותר לקטן ביותר, הפעמונים הם: סטפן הקדוש (5,700 ק"ג), לאופולד הקדוש (2,300 ק"ג), כריסטופורוס הקדוש (1,350 ק"ג), לאונהרד הקדוש (950 ק"ג), יוזף הקדוש (700 ק"ג), פטרוס קניסיוס הקדוש (400 ק"ג), פיוס העשירי הקדוש (280 ק"ג), כל הקדושים (200 ק"ג), קלמנט מריה הופבאור הקדוש (120 ק"ג), מיכאל הקדוש (60 ק"ג) וטארסיציוס הקדוש (35 ק"ג). עוד במגדל הדרומי הפעמונים "פרימגלוקה" (Primglocke, נוצק מחדש ב-1772) ו"אורשלה" (Uhrschälle, נוצק ב-1449), אשר מצלצלים בכל שעה עגולה.
המגדל הרומי הצפוני מכיל שישה פעמונים, חמישה מהם נוצקו ב-1772, והם מצלצלים לתפילות הערב ולציון הלוויות. אלה הם פעמוני העבודה של הקתדרלה, ושמותיהם מצביעים על שימושם המקורי: "פויירין" (Feuerin, "אזעקת אש", אך כיום משמש לקריאה לתפילות הערב) שנוצק ב-1859, "קנטרין" (Kantnerin, קורא לזמרים לתפילה), "פרינגרין" (Feringerin, משמש למיסה הראשית בימי ראשון), "בירינגרין" (Bieringerin, "צלצלנית בירה" ומשמש לקריאה אחרונה מהטברנות), "Poor Souls" ("הנשמות המסכנות", פעמון ההלוויות) ו"כורפטש" (Churpötsch, שנתרם בידי ציבור הבוחרים לכבוד האיקונין של מריה פטש שבקתדרלה).
השרפה ב-1945 הרסה את הפעמונים שנתלו במגדל הרומי הדרומי.
נאמר שהמלחין לודוויג ואן בטהובן הבין עד כמה הוא חירש כאשר ראה ציפורים שעפות החוצה ממגדל הפעמונים של הקתדרלה כתוצאה מצלצול הפעמון, אך לא יכול היה לשמוע את צלצול הפעמון עצמו.
אלמנטים נוספים.
ליד הקירות החיצוניים של הקתדרלה ניתן לראות:
פנים.
הקירוי הפנימי של חלל הקתדרלה הוא קמרון מסוג קמרון רשת הנראה כרשת של צלעות אלכסוניות בין העמודים הראשיים של המבנה.
מזבחות.
ישנם 18 מזבחות בחלק הראשי של הכנסייה, ועוד מזבחות בקפלות השונות. המזבח הראשי ומזבח וינר נוישטאדט הם המפורסמים ביותר.
המזבח הראשי.