Holtastaðarkirkja er í Bólstaðarhlíðarprestakalli í Húnavatnsprófastsdæmi. Holtastaðir eru fornt 
og kirkjustaður í Langadal. Þar voru katólskar kirkjur helgaðar heilögum Nikulási og þar var útkirkja frá Blöndudalshólum.
Árið 1880 var sóknin lögð til Hjaltabakka, til Höskuldsstaða 1881, síðan til Bergsstaða 1907 og loks til Bólstaðarhlíðar. Bárujárnsklædda timburkirkjan, sem nú stendur þar, var vígð 1893.
Jósafat Jónatansson, bóndi á Holtastöðum og Stefán Jónsson, bóndi á Kagaðarhóli kostuðu bygginguna. Yfirsmiður var Þorsteinn Sigurðsson frá Sauðárkróki. Altaristaflan er gömul, eftirlíking af kvöldmáltíðarmynd Leonardo da Vinci. Prédikunarstólinn með ámáluðum myndum gerði danskur maður, Simon Reifeldt, árið 1792. Merkur gripur úr kirkjunni, Vatnsljón eða vatnskanna í ljónslíki frá miðöldum, er nú í Þjóðminjasafninu.