História cirkvi na územi Vojnian siaha do 10. storočia, kedy bol na popud Noema Edena vybudovaný prvý kostol. Ide o ústnu tradíciu, ktorá hovorí, že na tomto mieste sa v roku 996 zastavil sv. Vojtech a pokrstil daného staviteľa. Preto bol na jeho počesť postavený na starom cintoríne kostolík (rotunda), ktorý bol v 12. storočí zbúraný. Jednoloďový gotický kostol bol nanovo postavený v prvej polovici 14. storočia a bol zasvätený sv. Kataríne Alexandrijskej.

Zaujímavosti
V interiéroch sa pôvodne nachádzal ranogotický tabernanákulový oltár zhotovený po roku 1300. Patrí medzi najzaujímavejšie stredoveké pamiatky v strednej Európe. Aktuálne sa tento oltár nachádza v Slovenskom národnom múzeu vo Zvolene pod inventárnym číslom P 141. V roku 1700 sa v kostole nachádzali tri oltáre. Hlavný bol zasvätený sv. Kataríne, bočné Blahoslavenej Panne Márii a sv. Mikulášovi. Hlavný oltár nevieme presne datovať, ale oltárny obraz pochádza z 2. polovice 19. storočia. Niektoré pramene uvádzajú, že oltár bol vyhotovený koncom 18. storočia. Pravý bočný oltár je zasvätený sv. Jozefovi (koniec 18. storočia). Bol darom katolíckého kostola zo Spišskej Belej. Ľavý bočný oltár je zasvätený sv. Barbore (koniec 18. storočia).