Kirken blev bygget som en del af det klosterkompleks, benediktinermunke i slutningen af 1000-tallet byggede i det Midtjyske Søhøjland.
Cistercienserordenen overtog i 1166 klosteret men blev dog ikke længe i Veng. Allerede i 1168 forlod de Veng Kloster og grundlage i 1172 Øm Kloster.
Af Veng Kloster er i dag kun kirken tilbage. Efter at cistercienserne havde forladt Veng Kloster, fik kirken status af sognekirke.
Kirken, som er opbygget i frådsten, er bygget i korsform. Kirken er stilren i sin arkitektur. Kor og apsis er enkelt, men smukt dekoreret. De smukke dekorationer på ydersiden af apsis er med til at understege bygningens funktion som alterhus. Korsarmene er i to stokværk med hver sis apsis.
Fra 2003 til 2005 var kirken lukket pga. en gennemgribende restaurering. I forbindelse med restaureringen blev kirkens altertavle fra ca. 1590 flyttet til kirkens søndre korsarm. Et tilmuret vindue blev åbnet og isat mosaikrude udført af billedhuggeren Erik Heide, Mors. Den favnende Kristus i støbejern bag alteret, er ligeledes udført af Erik Heide. Alterbordet står i pudset frådsten. De kalkfarvede felter på forsiden er påført alteret i 1500-tallet. Som bordplade er der i forbindelse med restaureringen lagt en stenplade udført i sort, svensk granit.