Wegen der noch mangelhaften Innenausgestaltung war eine feierliche Konsekration zunächst noch nicht möglich. Die neue Kirche sollte aber möglichst schnell ihrer Bestimmung nachkommen. Daher war eine einfache Segnung, eine sogenannte „Benediktion“ notwendig. Dadurch konnte in der Kirche die Heilige Messe gefeiert werden. Stadtdechant Konstantin Walter, der Pfarrer von Fünfhaus, benedizierte am 29. Dezember 1898 die Pfarrkirche „Zu Ehren Mariens, der Königin der Märtyrer, und zu Ehren des seligen Rudolf“. Am 30. Jänner 1889 hatte sich Kronprinz Rudolf, der einzige Sohn des Kaisers, in seinem 31. Lebensjahr in Mayerling erschossen. Das Gotteshaus sollte auch als Gedächtnisstätte für den Kronprinzen dienen – dieser ist jedoch nicht ident mit besagtem Seligen!

Das dreiteilige Hochaltarbild fertigte der Akademischen Maler Josef Reich an. Es zeigt Maria als Königin der Märtyrer – das Motiv des Namensfestes der Kirche – thronend auf einem Marmorsitz in der Bildmitte. Links von ihr steht der hl. Petrus und neben ihm der hl. Erzmärtyrer Stephanus, der Patron unserer Bischofskirche und Erzdiözese. Rechts neben der „Regina Martyrum“ (Königin der Märtyrer) erkenne wir drei Frauengestalten: eine Personifizierung von Glaube (Fides), Hoffnung (Spes) und Liebe (Caritas). Im linken Seitenbild sieht man Abel mit dem Opferlamm, den hl. Sebastian und kniend den seligen Rudolf von Bern (†1294). Im rechten Bild sind die hl. Katharina – eine der 14 Nothelfer/innen – und die hl. Cäcilia, Patronin der Kirchenmusik, dargestellt. Leider stellte sich später heraus, dass das Altarbild nicht – wie vereinbart – auf Schweinsleder, sondern nur auf eine einfache Leinwand gemalt worden war. Darunter litt die Qualität des Bildes sehr.