Urkundlich scheint vor 1122 in St. Veit eine dem gleichnamigen Heiligen geweihte Kirche mit Friedrich von der Hohenstaufe als Vogt auf. Das Gotteshaus war von seinem Gründer, Markgraf Otakar II. von Steyr, und dessen Gefolgsleuten so reichlich ausgestattet, dass hier ein Priester erhalten werden konnte. Die Einkünfte der St. Veiter Kirche bestanden aus den Abgaben höriger Bauern und aus eigenem Wirtschaftsbesitz. Ob die zwischen 1100 und 1110 erbaute Kirche schon ein Steinbau war, lässt sich nicht nachweisen, doch Bischof Altmann von Passau begann schon in dieser Zeit in seinem Gebiet die Holzkirchen durch feste Bauten zu ersetzen. Mit dem 1083 geweihten Stift Göttweig, dessen Gründer Altmann war, ist St. Veit seit 1161 verbunden, als der steirische Markgraf Otakar III. seine Eigenkirchen in St. Veit und Hainfeld gegen Besitz in Alkersdorf dem Stift überließ. St. Veit bestand als eigene Pfarre bald nach 1161.
Das 15. Jahrhundert brachte auch den gotischen Ausbau der Pfarrkirche - ältester Teil ist der um 1400 entstandene Chorrraum, das Langhaus wurde um 1470 gebaut. Auch wesentliche Kunstschätze gehören dieser Epoche an, so "Christus als Lehrmeister mit den 12 Aposteln", der Schmerzensmann an der kunstvollen Orgelempore, und das Rundfenster mit Christuskopf. Aus dem 16. Jahrhundert stammen das riesige Kruzifix und die Madonnenstatute auf dem neugotischen Marienaltar. Bemerkenswert sind die Rippengewölbe und die Maß-Werke der gotischen Fenster, die in der Barockzeit teilweise vermauert wurden. Im 17. Jahrhundert wurde nur mehr ein bereits vorhandener gotischer Nordwestturm ausgebaut, der bis zum Dachgeschoß auch Wehrcharakter hatte. Trotz der Lage in der Ebene werden Kirchen oft als Wehranlagen angesehen. Sicher war der Kirchhof mit dem Freudhoftor (GH Wittmann) ummauert, aber wehrhaft erscheint eigentlich nur die gegen die Gölsen gerichtete Steinmauer des ehemaligen Pfarrhofgartens, die 1912 noch mit Schießscharten versehen war.
Erst in der Zeit Maria Theresias kam es wieder zu vermehrter Bautätigkeit in der Kirche. Anlässlich der Renovierung von 1763 bis 1771 entstand der neue Hochaltar. Die Kirche hatte schon seit dem 17. Jahrhundert eine Kirchturmuhr und eine Orgel. Das heutige Aussehen erhielt das Gotteshaus durch den 1831/32 nach Entwurf von P. Koloman Viest umgebauten Trumhelm. Nachdem schon 1826 ein neuer Friedhof außerhalb des Marktes angelegt worden war, ließ man 1830 den Friedhof um die Kriche auf.1891 kam es zur Regotisierung der Pfarrkirche, es folgte die Innenausmalung. Es wurde die vermauerten Maßwerke der Fenster ausgebrochen und später mit den von Ortsbewohnern gestifteten Glasmalereien versehen. 1900/01 erhielt das Westportal ein gemauertes Vorhaus, die Kirche ein neues Ziegeldach, während der Zwiebelturm bis 1963 mit Holzschindeln gedeckt blieb. 1910 wurde elektrische Leitungen installiert. 1921 war die Weihe neuer Glocken, 1926 bis 1928 konnte die Kirche und der Pfarrhof renoviert werden, 1927 weihte man das an der Kirche angebrachte Kriegerdenkmal. 1968 bis 1970 erfolgt die neuerliche Renovierung des Daches und der Innenräume. Mit dem Bau der Umfahrungsstraße kam es schließlich 1970/71 zur Errichtung des neuen Pfarrhofes. Die Orgel wurde 1975 nahezu erneuert.
