Die Pfarrkirche Gutenstein wurde wie die Burg von Herzog Leopold VI. erbaut. Sie scheint 1476 im Verzeichnis der Passauer Diözese erstmals auf. Seit 1913 ist die Pfarre Gutenstein in das Dekanat Piesting der Erzdiözese Wien eingegliedert.

Von der ursprünglich gebauten Kirche 1220 sind heute noch im Bereich des Turms und der Orgelempore Bruchsteinmauern dieser Zeit erhalten. Die Größe der damaligen Kirche entsprach etwa der Größe des heutigen Hauptschiffes.

Im Laufe der Jahrhunderte wurde die Kirche laufend ausgebaut:

1487: Das Gotteshaus wurde nach Westen hin um den gotischen Chor erweitert.

1675–1680: In der dritten Bauphase wurde das Hauptschiff neu erbaut und dessen Gewölbe mit dem gotischen Chor unter einer Dachgleiche gebracht. Die Außenwände wurden mit Strebepfeilern verstärkt.

1784  Der Katharinenaltar mit den beiden Statuen der hl. Margarete und hl. Barbara wurde aus der Burgkapelle in die Pfarrkirche verfrachtet. Der zweite Seitenaltar wird von den beiden Statuen des hl. Florian und Bischof Eligius flankiert.

1834  Der ehemalige Friedhof des Marktes Gutenstein wurde in diesem Jahr aufgelassen. Er befand sich rund um die Kirche. Der neue Friedhof wurde am Nordhang des Mariahilfberges, auf der sogenannten "Köferwiese" angelegt.

1857  Der Turm wurde erhöht, das Oratorium im Norden wurde angebaut und die heilige Grabkapelle errichtet.

1897 Der alte Pfarrhof von 1220 bestand bis kurz vor Ende des 19. Jahrhunderts. War er schon mehr als baufällig gewesen, so wurde der Pfarrkirche erst ziemlich spät ein neuer Pfarrhof zugestanden.

1907 Die gotische Sakristei wurde abgetragen und durch den heutigen Neubau ersetzt.

Im 19. und 20. Jahrhundert wurden die Glasfenster ausgeschmückt und zeigen seitdem die wunderschönsten Bilder. So kann man im Chor die "Verkündigung Mariens" (1899) und die "Flucht nach Ägypten" (1899) bewundern. Auf der linken Seite befindet sich das Bildnis des hl. Aloysius (1904 von Aloysia Tyrolt gestiftet) und rechts kann man die hl. Rosa von Lima sehen. Im Schiff links befindet sich die Darstellung der hl. Elisabeth von Thüringen (1932) und rechts von der hl. Cäcilia (1910).