A település főutcájának kiteresedésében, az egykori kastélykertek szomszédságában álló, keletelt, támpillérekkel gyámolított, poligonális záródású, egyhajós, gótikus teremtemplom. Nyugati oldala előtt háromszintes, fiatornyos, gúlasisakkal fedett torony áll.
Egy, a 13. század végén épült kis templom helyére a 16. század elején épült a jelenlegi templom, lebontva elődjének szentélyét és sekrestyéjét. Az új épülethez sokszögzáródású, sarkain támpillérekkel erősített, kőbordás, hálóboltozatos szentélyt és egy nagyobb sekrestyét is emeltek. Tornyát 1791 után állították, a sisak fiatornyai 1892-ben készültek.
A vajai templomot a reformáció kezdete óta birtokolja a református gyülekezet, amelynek legnagyobb patrónusa a földesúri jogokat gyakorló Vay család volt, így kerülhetett Vajai Vay Ádám, II. Rákóczi Ferenc udvari főkapitányának epitáfiuma a templombelsőben elhelyezésre. Ugyanez a család adományozott értékes klenódiumokat is az egyház számára, mely közül többet a Sárospataki Református Kollégium gyűjteményében őriznek. Az empire stílusú szószéke és Mózes-széke 1837-ben készült.
Száz Magyar Falu. Vaja. Írta: Göőz Lajos, Németh Péter, Takács Péter, Bene János, Páll István és Molnár Sándor. Szerkesztette: Németh Péter. Száz Magyar Falu Könyvesháza Kht. Budapest, 2001.