Kirkja hefur að öllum líkindum verið í Stóra-Dal frá kristnitöku á bæ Runólfs goða. En fyrsta heimild um hana er að finna í kirkjuskrá Páls Jónssonar biskups.
Stóra-Dalskirkja þjónar Stóra-Dalssókn sem er vestan Holtssóknar og nær frá og með Fit og Fornusöndum að StóruMörk, auk Hólmabæja, vestan Markarfljóts. Prestakallið var síðan sameinað Holtsprestakalli 1867 og hefur verið þjónað þaðan síðan.
Fram til ársins 1924 var Stóra-Dalskirkja bændaeign en eftir það afhent söfnuðinum.
Fyrsta timburkirkjan var byggð 1843 innan núverandi kirkjugarðs, og má glögglega sjá hvar hún stóð. Hún var svo rifinn og önnur járnklædd timburkirkja byggð á sama stað árið 1895, og stóð hún til ársins 1970. Þá var kominn tími á að reisa nýja kirkju. Henni var valinn staður sunnan kirkjugarðsins og var hún reist á árunum 1964 til 1969. Kirkjuna teiknaði Ragnar Emilsson arkitekt. Hún er ekki í hinum hefðbundna kirkjustíl, en samt sem áður mjög falleg og hlýleg. Sá sem var yfir smíðum hennar var Þorsteinn Jónsson frá Drangshlíðardal.
Kirkjan var síðan vígð 1969 af séra Sigurbirni Einarssyni biskupi.
Altaristafla kirkjunnar er eftirmynd Sigurðar Guðmundssonar málara af altaristöflu Dómkirkjunnar í Reykjavík sem máluð var af Wegener 1847 og sýnir upprisuna. Taflan var áður í Voðmúlastaðarkirkju.