Первая, Троицкая, церковь была перевезена в Вену в 1762 году по просьбе посла князя Д. М. Голицына из Аугсбурга. В храме был иконостас «на голубой камке». Церковь была размещена в доме князя, а затем «в особливой гостинной». В 1781 году церковь переехала в другое, но тесное и плохо освещённое место. В 1803 году храм перенесли в новое, более приспособленное место, а в 1812 году — в дом на Вальфишгассе, 5. Храм построен как посольский (при российском Императорском Посольстве) в 1893—1899 годах по проекту Григория Ивановича Котова итальянским архитектором Луиджи Джакомелли.
Значительная часть расходов на строительство (400 000 рублей) составили пожертвования Императора Александра III.
Освящён 4 апреля 1899 года архиепископом Холмским и Варшавским Иеронимом (Экземплярским).
После начала Первой мировой войны (1914), ввиду разрыва дипломатических отношений между Россией и Австрией, посольство и собор были закрыты и состояли под охраной нейтральной державы — Испании. В начале 1921 года храм осмотрел архиепископ Евлогий (Георгиевский), в конце 1920 года назначенный постановлением ВВЦУ ЮВР управляющим западноевропейскими русскими церквами, и нашёл его в полном запустении. Митрополит Евлогий последовательно сменил на приходе нескольких настоятелей, тем не менее констатировал: «Приход в Вене маленький, слабенький, едва влачит существование.» Митрополит Евлогий вместе со своими приходами перешёл в феврале 1931 года в юрисдикцию Константинопольского Патриархата (Западноевропейский экзархат русских приходов).
После начала Великой Отечественной войны в июне 1941 года, вся недвижимость советской дипмиссии в Вене (дипломатические отношения были прерваны после аншлюса Австрии в марте 1938 года и её присоединения к Германии), включая собор, была конфискована Внешнеполитическим ведомством Германии и передана в пользование Имперской высшей музыкальной школы города Вены (ныне Венский университет музыки и изобразительного искусства).
19 мая 1943 года собор был передан во временное пользование общине РПЦЗ во главе с полковником в отставке Георгом фон Генюком.
В октябре 1945 года храм, полностью сохранившийся (в отличие от здания посольства), был открыт как приход Московского Патриархата прибывшим для сего из Москвы архиепископом Фотием (Топиро); в 1946 году в Вену был назначен епископ Сергий (Королев) — как викарий Патриаршего Экзарха в Западной Европе.
В 1962 году, ввиду учреждения Священным Синодом Русской Православной Церкви Венской и Австрийской епархии (юридически признана правительством Австрии в 2012 году), храм стал именоваться кафедральным собором.
С 1975 до 1999 года правящим архиереем Венско-Австрийской епархии был архиепископ (затем митрополит) Венским и Австрийский Ириней (Зуземиль). 19 мая 1969 года приход собора был признан юридическим лицом.
С 2003 по 2008 год в соборе проводился капитальный ремонт (основными спонсорами были Российская Федерация, нефтяная компания «Лукойл», магистрат города Вена, Министерство культуры Австрии и компания «Газэкспорт», компания «Моссиб»), по окончании которого планировалось освящение обновлённого храма в рамках официально анонсированного в конце ноября 2008 года визита приснопамятного Святейшего Патриарха Московского и всея Руси Алексия II в Австрию, намечавшегося на 20—23 декабря. Однако вместо него 21 декабря 2008 года была совершена панихида по скончавшемуся Патриарху Алексию II.
Настоятель собора в настоящее время — епископ Венский и Австрийский Алексий.