A Kürtösi családból származó Zólyomi Tóbiás comes 1242-ben Dalmáciba kísérte a tatárok elől menekülő IV. Bélát. Az ő egyik fia, Bitó (Bythou, Bytho) részt vett III. András oldalán a Borsa-fiak lázadásának leverésében, és Adorjánvára ostromakor súlyos sebeket szerzett. Bitó és fivére, Zobratha comes (egy ízben Madách-Zobratha) harci érdemeik jutalmául nyerték a rokonaik birtokaival szomszédos Zolnát a vele szomszéd Számpor egy részével együtt.
1311-ben Tamás esztergomi érsek engedélyezte Bitó és Zobratha comeseknek, hogy Zolnán Szent István első vértanú tiszteletére templomot alapítsanak. Az épület azonban régebbi, és a szakértők 1260-1280 közötti időszakra datálják.
Bitót 1312-ben Radványi Tamás zólyomlipcsei várnagy — a Radvánszkyak őse — meggyilkolta. Fivére, Zobratha comes is fiú utód nélkül halt el. Zolnát unokafivérüknek, Oszlári Madách fiának, Benedeknek (1278-1328) fia, Zolnai Tamás örökölte.
Az 1332-és és 1337-es pápai tizedjegyzék szerint a falu plébánosa János volt, aki 4 márka adót fizetett ("Johannes plebanus Sancti Stephani 4 marcas solvit"). 1347-ben Miklós zolnai plébános a buda-felhévizi keresztesekkel átíratja Bitó és Zobrata ispánoknak a zolnai egyház alapítására vonatkozó kiváltságlevelét.
Zolnai Tamás után a birtok 1351-ben a fiági Kürtösi atyafiaknak, nevezetesen Madách fia Pálnak unokáira, az árva János fiaknak - Jakab mesternek (János fia Jakab mester 1402-ben a király ügyvédje), Péternek, Kelemennek, Domonkosnak, Istvánnak — kezére jutott. Egyikük a 15. századtól Zolnán továbbélő családnak őse.
A 14. század végétől fogva a I. Lajos király alapította véglesi királyi uradalomnak tartozéka lett, viszont a templom kegyúri jogai megmaradtak 1709-ig a Zolnai család kezében (1561 körül evangélikussá lettek és a templomot csak 1709-ben veszik vissza a katolikusok).
A templom egyhajós, keletelt, sokszög záródású szentéllyel. Nyugati oldalán torony van amelyet kitört ablakosztójú román kori ikerablak-keretek díszítenek (mára ezt kiegészítették 2022). A korábbi templom hajójának falait 1311-ben megemelték, gótikus boltíveket kapott. A sekrestye további bővítéséről tanúskodik a presbitérium egyik nehéz támpillérének alsó része is, amely most annak belsejében van. A templom külső homlokzatát fehérre festették és piros négyzetekkel egészítették ki. Az 1360-1390 közötti időszakban a templom belsejét gótikus freskókkal díszítették, amelyek közül néhányat a mai napig látható. A hajó északi falán a Passió-ciklus képei vannak, melyek közül a Levétel a keresztről és a Feltámadás a legszebbek. Az itt látható Szent György kép a kutatók szerint a templom legrégebben készült freskója. A diadalívet Szent Valentin és Szent Miklós püspökök képével díszítették. Érdekesség, hogy a freskók készítőinek nevét megörökítették: " ...-nak fia; Miklós, Maso-nak fia és János Querhen-nek fia több társukkal egyetemben készítették ezt a képet". A legfiatalabb festmények valamikor a 16. század elején kerültek a templomba. Értékes régi emléke a zolnai templomnak egy — külön haranglábon álló - harang. Ezt latin nyelvű felirata szerint 1514-ben öntötték.
A 16. század folyamán a presbitérium szerkezetét a sarkokon tartóoszlopokkal erősítették meg, a templomot a török veszély miatt lőréses kőfallal vették körbe. Miután a katolikusok 1709-ben visszavették a templomot új védőszentet kapott: Szt. Mátyást. A 17. század végén a hajó nyugati részébe fából készült karzatot építettek és barokk bútorokkal rendezték be.
A templom 1944-ben a harcokban megsérült. A háborús találatok a torony és a hajó déli oldalát, a hajó tetőszerkezetét, a sekrestye keleti oldalát érték. Itt az egész gótikus boltozat lezuhant. A háború után a templom őrizetlen és elhagyatott volt, ismeretlenek a freskókat is megrongálták. 1948-ban a szentély kupoláján az 1400-as évekre tehető freskódíszeket fedezték fel: a kupola festett boltívének ívmezeiben négy magyar szent, Szent László, Szent Imre, Szent István és Szent Erzsébet volt látható. Sajnos a szentély egész kupoláját 2009-ben lemeszelték, így ez most nem látható. Az 1970-es években a templomot restaurálták. Ekkor eltávolították a sarokpilléreket, míg a festmények restaurálása csak az 1990-es években fejeződött be. 1993-ban régészeti kutatást is végeztek. Az épület komplex felújítása 2011-ben kezdődött.
Források: Zolnay László: A Madách család eredete (Nógrád Megyei Múzeumok Évkönyve IX., 1983); Zolnay László: A régi zólyomi ispánság építkezéseinek történetéhez 3. Közlemény (Ar Hunrarica, 1978/2);
A település főutcáján lehet parkolni, egy földút vezet a templomhoz. 1-2 perces séta.
Szélesség: N - 48°36'07.0"
Hosszúság: E - 19°13'29.5"