Die Pfarre Pottendorf wurde im 12. Jahrhundert gegründet. Von 1558 bis 1628 stand die Pfarrkirche unter dem Patronat des protestantischen Schlossherrn Zinzendorf-Pottendorf und Königsberg. Die Vorgängerkirche stand vermutlich im östlichen Teil des Parkes vom Schloss Pottendorf und wurde abgetragen. Die neue Pfarrkirche wurde von 1714 bis 1718 im Auftrag von Gundaker Thomas Starhemberg durch den Baumeister Franz Jänggl nach den Plänen des Architekten Johann Lukas von Hildebrandt errichtet.
Der mächtige hochbarocke kreuzförmige Zentralbau mit Einturmfassade dominiert den Kirchenplatz. Die Kirche ist an drei Seiten von einer Kirchhofmauer mit Skulpturen umgeben. Im Jahre 1769 wurde unter dem Baumeister und Pfarrer Johann Josef Zisser eine Vorhalle zugebaut und die südliche Sakristei um eine Paramentenkammer erweitert, wobei die Kirchhofmauer im Westen entfernt wurde.
