Altenmarkt wurde urkundlich das erste Mal 1233 bzw. 1234 erwähnt, als  Leopold von Blumenau das Dorf an die Johanniter (später Malteser) verschenkte. Um 1240 / 1250 haben die Johanniter eine Kirche errichtet, und zwar im romanischen Stil. Als Patronin fungierte Maria in der Au, wodurch dieses Gotteshaus auch zu einer Wallfahrtskirche wurde.

Ende des 13. Jahrhunderts bzw. zu Beginn des 14. Jhdts. wurde die Kirche erstmals kräftig umgebaut: Im gotischen Stil wurde das Presbyterium (mit Fresken und Spitzbögen) angebaut, eine holzgetäfelte Flachdecke eingezogen und ein niedriger Turm an der Westseite vorgestellt.

Etwa 1662 bis 1667 erfolgte eine barocke Umbauphase mit Verbreiterung des Kirchenschiffes nach Süden hin, die hölzerne Flachdecke wurde abgetragen und durch das noch heute sichtbare Gewölbe ersetzt. Der gotische Turm wurde aufgestockt und mit einem Zwiebelhelm gekrönt. Die bereits an der Südostseite angebaute Sakristei wurde 1770 aufgestockt, wodurch die südseitigen Fresken großteils zerstört wurden.

Am Ende des 2. Weltkrieges wurde die Kirche nicht stärker beschädigt, obwohl im Pfarrhofbereich zumindest 3 Granattreffer einschlugen (beim dritten wurden 4 Personen getötet, weitere verletzt).

Die letzte große und umfassende Restaurierung wurde 1986 beendet.

Kirchenpatron Hl. Donatus: Nach der Zeit um Kaiser Joseph II. (gest. 1790) dürfte der hl. Donatus als Pfarrpatron „Maria in der Au“ abgelöst haben.