Vermutlich Salzburger Missionare des 9. Jahrhunderts errichteten auf Göttweig eine Kirche zu Ehren der Hl. Erentrud. Diese  wurde von Bischof Altmann 1072 neu geweiht.
Als Altmann über ein Patrozinium für das Gotteshaus des von ihm gegründeten Stiftes Göttweig nachdachte, schienen ihm Petrus oder Michael gelegen. Doch er besann sich eines Besseren, als ihm der böhmische Herzog eine Marien-Ikone schenkte: „Gleichsam als wäre dieses Bild auf göttliche Weisung geschickt worden, verehrte es der gottgeliebte Bischof mit einem Kuss, stimmte das Te Deum laudamus an und weihte die Stätte alsogleich der hl. Maria. Die Tafel aber hing er auf einer Eiche auf, die so lange vor dem Altar stehen blieb, bis er den Bau des Gotteshauses zu Ende geführt hatte.“ Die Stiftskirche wurde am 9. September 1083 geweiht.
In das Jahr 1083 reichen die Anfänge der Pfarre zurück, um 1130 wurde eine eigene romanische Pfarrkirche St. Gotthard neben der Stiftskirche errichtet, an deren Stelle man 1403 bis 1414 eine gotische Pfarrkirche erbaute (ebenfalls dem Hl. Gotthard geweiht, im Volksmund jedoch „Altmanni-Kirche“ genannt), die beim Stiftsbrand 1718 schwer beschädigt und in der Folge abgerissen wurde.
Von da an war die Stiftskirche gleichzeitig Pfarrkirche – bis zum 12. September 1993. An diesem Tag wurde die neue Pfarrkirche St. Altmann im Hellerhof geweiht und zum Sitz der Pfarre erklärt.
Am Tag der Grundsteinlegung der neuen Pfarrkirche, dem 16. Juni 1991, wurde der Name der Pfarre von „Göttweig“ in „Paudorf-Göttweig“ geändert.