Die dem Heiligen Augustinus geweihte Pfarrkirche von Perchtoldsdorf zählt mit der anschließenden Herzogsburg zu den bemerkenswertesten Kirchenfestungen in Österreich. Sie war ursprünglich die Burgkapelle (1217 Pfarrerhebung) und befindet sich daher
innerhalb der Burgbefestigung.
Im Zuge der Errichtung einer Herzogsburg um 1340 unter Herzog Albrecht II. erfolgte 1335 bis 1338 der Zubau der sog. Herzogskapelle (heute südl. Seitenchor). Im Anschluss daran wurde der romanische Bau abgebrochen und ein repräsentativer dreischiffiger Chorneubau (Staffelchor) errichtet (Weihe 1362). Der gotische Bau orientiert sich in vieler Hinsicht am Vorbild des Albertinischen Hallenchors von St. Stephan in Wien, weshalb eine Beteiligung des Herzogs an der Finanzierung des aufwändigen Vorhabens angenommen wird. 
Etwa 100 Jahre später, ab 1435, erfolgte unter Pfarrer Thomas Ebendorfer der Bau des gleich breiten, aber wesentlich höheren spätgotischen Hallenlanghauses, das 1449 geweiht wurde.