Velemért a Szentháromság tiszteletére szentelt templomával együtt először 1360-ban említik az írott források. A középkori falu a templom körül lehetett.

A templom építésének idejét nem ismerjük, az azonban biztos, hogy sokszögzáródású szentélye, mérműves ablakai és körtetagos profilú kapuja nem másodlagos átépítés során készültek. A gótikus templomnak tehát román kori előzménye nem volt. Nyugati tornyával, síkmennyezetes hajójával, diadalívvel elválasztott, alacsonyabb, boltozott szentélyével azonban a korábbi, 12–13. századi templomépítészet hagyományait őrzi.

Az épület sarkait gondosan faragott kváderkövek erősítik, a vakolt téglafalakban megfigyelhetők az építési állványok lyukai. A hajón ívsoros párkány fut körbe, négy sarkán emberfejekkel. Egyikük hegyes sipkás, portrészerű figura.

A 17. század közepén a templom a protestánsok használatába került, ezért a falképeket részben lemeszelték. 1733-ban a katolikusoké lett, de 1808-ban már annyira rossz állapotban volt, hogy nem használták. A veleméri templom és falképeinek megmentése a magyar műemlékvédelem történetének egyik első fejezete. Rómer Flóris bencés szerzetes, a műemlékvédelem legendás alakja, 1863-ban talált a tető nélkül romosodó templomra: „benne a páfrány és csipkebokor bujálkodik – a marhaganéj és tüzihelyek arra mutatnak, hogy itt Isten szentélyében a pásztorok menhelyet találnak és az Isten házát folytonosan profanálják”. Rómer közbenjárására tető épült, és a falképekről színes akvarellmásolatok készültek, hogy könyvekben, kiállításokon a nagy közönség számára is megismerhetők legyenek. 1894-ben, 1904-ben és 1927-ben ismét javították az épületet, de a freskók restaurálására csak 1937-ben került sor. A templomot és a falképeket legutóbb 1966–68 között restaurálták.