Middelalderkirka i Stordal var ei stavkirke som stod på samme plass som dagens kirke som er fra 1789. Kirka er nevnt i Aslak Bolts jordebok og Hans Strøm gav i 1766 en beskrivelse av kirken som en liten og uannseelig stavkirke som eide veldig lite land.
Eldste omtale av kirken er i 1432 (Stoladals kirkio, AB 133). Den eldste kjente kirken på (gnr. 130) Kirkebøen skal ha vært en rektangulær stavbygning uten utvendig skille mellom kor og skip, med utvendige mål 20,5x8,5 m. I sør var det et våpenhus som målte 3,9 m i kvadrat, og bygningen skal ha hatt svalganger – i 1727 mot nord og øst. Ved flere anledninger er bygningen blitt skordet opp. I 1788 ble den gamle stavkirken revet og nåværende kirke sto ferdig året etter, som det ser ut til på samme tuft som den eldre.