Bereits um 1243 wird hier eine Kirche erwähnt, welche dem Stift Klosterneuburg angehörte und bereits im 14. Jrh. zur Pfarrkirche erhoben wurde (eine Zahl im Chor nennt sogar das Jahr 1095). Es dürfte sich um eine romanische Saalkirche gehandelt haben, welche später gotisch umgestaltet wurde. Die Pfarre Heiligenstadt war sehr bedeutend, denn ihr Einzugsgebiet war gross und umfasste sämtliche umliegende Dörfer. Als diese nach und nach ihre eigenen Pfarren bildeten, verlor die Pfarre Heiligenstadt an Wichtigkeit. Die Türkenkriege brachten auch über Heiligenstadt grosse Verwüstungen, worauf die Pfarrkirche wieder aufgebaut werden musste. Im Jahre 1723 wurde sie barockisiert und blieb so bis ans Ende des 19. Jrh. bestehen. Dann jedoch war sie so baufällig, dass sie fast vollständig demoliert werden musste, einzig der Chor und die Grundmauern blieben bestehen.
Der Architekt Richard Jordan wurde mit dem Neubau der Kirche beauftragt, welche dem Vorgängerbau bis auf den Glockenturm nachempfunden ist, weshalb der neugotische Stil nicht auf Anhieb erkennbar wird. Das Relief im Spitzbogen über dem Eingangsportal zeigt den Erzengel Michael. Links vom Portal befindet sich ein Sockel, auf welchem die Statue des Brückenpatrons Johannes-Nepomuk steht. Die Figur stammt aus dem frühen 18. Jrh. und befand sich ursprünglich an der nahen Brücke über den Grinzinger Bach. Die Staffelkirche ist dreischiffig. Der frühere Hochaltar war das Werk von Matthias Steinl und wurde in die Pfarrkirche Leopoldau versetzt. Zentrum des heutigen Hochaltars ist das Bildnis des hl. Michael. Der Sebastiansaltar ist das einzige Relikt der ehemaligen barocken Ausstattung der Vorgängerkirche.