Kirkja hefur staðið í Stafholti frá fornu fari. Hún var helguð heilögum Nikulási.
Þess er getið í máldaga frá 1140 að Steini Þorvarðsson prestur hafi gefið staðinn sem beneficium, þ.e. sem prestssetur. Aðrar eignir sem staðurinn átti og hafði tekjur af skv. máldaganum voru Svarfhóll, Bjargarstein, Hofsstaðir, Laxholt, Skógaland (þ.e. Litluskógar) og Engines á Ströndum. Þá átti kirkjan einnig Stafholtsey en hún var látinn í makaskiptum upp úr 1880.
Í úttekt sem gerð var á staðnum 1887 eru nefndar þessar fasteignir, ítök og hlunnindi Stafholtsprestakalls: Vatnshamrar í Andakíl, Neðranes, Hofsstaðir, Bjargarsteinn, Svarfhóll, Melkot, Flóðatangi, Laxholt, Litluskógar, Grísartunga, ½ Kaldakinn í Dalasýslu, Engines á Ströndum, Sauðhúsapartur, Bjarnardalur og Staðarmúli, Hrísey í Hreðavatni, Kirkjuholt í Skarðshala, Þræley, selför í Þverárdal ofan Kvía, skógur í Skorradal (svonefndar Kirkjutungur), kerveiði undir Laxfossi í Norðurá, tveir eða þrír hlutir allrar veiði í Þverá, öll veiði í Móhyl í Gljúfurá, Staðartunga, selland. Vegna þessara hlunninda þótti Stafholt alltaf eftirsóknarvert prestakall, í röð hinna betri.
Þrátt fyrir að á staðnum sætu prestar, þá virðast leikmenn hafa haft ráð á honum um tíma. Meðal annars bjó Snorri Sturluson þar um þriggja ára skeið, svo og Ólafur Þórðarson hvítaskáld.
Núverandi kirkja í Stafholti var reist á árunum 1875-1877 og var með allra stærstu og glæsilegustu sveitakirkjum á sínum tíma. Í upphafi var þakturn á kirkjunni með dómkirkjukraga og lítil forkirkja. Prestur í Stafholti var þá sr. Stefán Þorvaldsson og stóð hann fyrir byggingunni. Kirkjan var afhent söfnuðinum til eignar og umsjár 1910. Sagt er að Björn Ásmundsson á Svarfhóli hafi flutt eitthvað af kirkjuviðnum utan af Akranesi í flota, sem síðan var slefað alla leið upp að Stafholti eftir Hvítá og Norðurá.
Kirkjan rúmar um 100 manns í sæti. Það einkennir hana að hringhvelfing er yfir kór og skilrúm milli kórs og kirkjuskips. Kirkjunni var breytt nokkuð 1948, reist ný forkirkja og turn settur á hana. Við það breytti hún nokkuð um svip hið ytra en varð á margan hátt rúmbetri og reisulegra hús.
Kirkjan á þessa gripi helsta: Altaristöflu sem Einar Jónsson myndhöggvari málaði og gaf kirkjunni, líkl. 1958. Kom hún í stað annarrar sem Þorsteinn Guðmundsson frá Hlíð í Gnúpverjahreppi hafði málað. Kaleikurinn er eftir Sigurð Þorsteinsson, íslenskan silfursmið sem starfaði í Kaupmannahöfn og var einhver þekktasti silfursmiður í Danmörku um sína daga. Er kaleikurinn með ártalinu 1748. Oblátuöskjur eftir Eggert Guðmundsson í Sólheimatungu. Skírnarfonturinn er eftir Ágúst Sigmundsson.
Tvær klukkur eru í turni. Önnur ber ártalið 1739 og er letrað á hana Jón Jónsen, Stafholti. Er hér án efa um að ræða sr. Jón Jónson sem prestur var í Stafholti á þessum tíma.
Í Stafholtssókn voru allir bæir í Miðtungu nema Hjarðarholt, Bakkakot og Einifell, sem lögðust til sóknarinnar 1991, Ystatunga og bæir í Borgarhreppi ofan til Eskiholts, Gufuár, Staðarhúsa, Laxholts og Litlafjalls.
Kirkjan var friðuð 1. janúar 1990 samkvæmt aldursákvæði 1. mgr. 36. gr. þjóðminjalaga nr. 88/1989.
