Norðtungukirkja var í kaþólskum sið helguð heilagri Katrínu. Kirkjunnar er fyrst getið í rituðum heimildum í kirknatali Páls Jónssonar Skálholtsbiskups frá því um 1200.
Fyrsti máldagi kirkjunnar sem varðveist hefur er talinn vera frá 1367. Samkvæmt honum átti kirkjan land á Högnastöðum. Í Gíslamáldaga, frá 1570, er kirkjan talin eiga Örnólfsdal að hálfu leyti og skóg í Kirkjuholti. Í jarðabók Árna Magnússonar og Páls Vídalín segir, að kirkjan og eigandi hennar eigi Örnólfsdal, sem þá hafði verið byggður úr selstöðu fyrir tæpum 40 árum.
Fram til 1911 var Norðtungukirkja útkirkja frá Hvammi í Norðurárdal, en það ár sameinuðust Hvamms- og Stafholtsprestaköll, um leið og sr. Gísli Einarsson flutti frá Hvammi að Stafholti.
Norðtungukirkja var flutt af sínu forna kirkjustæði þangað sem hún nú stendur árið 1879. Áður stóð hún í gamla kirkjugarðinum sem var norður af Norðtungubænum á bakka Þverár, nálægt þeim stað þar sem kirkjugarðurinn er nú. Kirkjugarðurinn var á sínum tíma færður vegna landbrots. Reist var timburkirkja þar sem stóð til 1952. Þá var hún tekin ofan og ný kirkja reist á sama stað. Kirkjan stendur spölkorn frá bænum, á bakka Þverár, en kirkjugarðurinn er allmiklu norðar, í miðju túni.
Núverandi Norðtungukirkja er steinsteypt. Hún var reist 1952 og vígð af sr. Bjarna Jónssyni árið 1953. Hún er stæðilegt hús með nokkuð háum turni á forkirkju og sönglofti. Hún er múrhúðuð að innan og máluð. Hún tekur 50-60 manns í sæti en stærð hennar að innan er 7,50 x 4,80m, stærð forkirkju (stöpuls) er 2 x 2m.
Kirkjubekkir, prédikunarstóll og altari eru úr gömlu kirkjunni, eins og altaristaflan sem kirkjan eignaðist skömmu fyrir aldamótin 1900. Kirkjan á tvær gamlar klukkur og koparstjaka.
Kirkjan er hituð með rafmagni. Árið 1990 var kirkjan einangruð og klædd að utan með stáli.