Den nåværende kirken fikk sin form og utseende etter en brann 1804. Kirken var opprinnelig en romansk steinkirke, trolig reist i første halvdel av 1100-tallet, med rektangulært skip og et smalere, tilnærmet kvadratisk kor og et kraftig tårn i vest. Så vel et steinsakristi i korets forlengelse mot øst som de to korsarmene som ble påbygd skipet – den nordre bygd 1674 med stein fra den gamle ødelagte Kiøbstad Hammer – er etterreformatoriske (Schøning II:29, Bugge 1957:454f).
Kirketuftens lokalisering og avgrensing er uavklart. Spor etter stedet der den gamle kirken på Vang skal ha stått er ikke synlige. Kirken ble i 1841 solgt til Tyskland og står i dag i Polen. Den er fra ca år 1190. Ifølge Magnus Olsen skal den gamle kirken ha stått der kirken står i dag. Folk i bygda, bl.a. Ola Haugen, tidligere kirketjener i Vang kirke, mener imidlertid at den skal ha stått noe nærmere veien (E68) og noe Ø for dagens kirke. Den skal ifølge sognepresten, med referanse til eldre billedmateriale, ha stått mellom nåværende kirke og hovedveien i sør.
Den middelalderske steinkirken står på på tangen mellom Prestvannet i øst og Brastadvannet i vest. Den opprinnelig romanske bygningen hadde fram til 1848 rektangulært skip og smalere, rektangulært kor med apsidal avslutning. Nåværende våpenhus i vest er trolig nedre del av et middelaldersk vesttårn. I 1848 ble koret og skipets østvegg revet og erstattet av et stort, korsformet tilbygg (Meberg 1987). Kirkens nåværende spissbuede portaler har derimot tidliggotiske stilpreg fra 1200-tallet og er rimeligvis sekundære.
Kirken er også omtalt som Lista kirke 1. Nåværende kirke er gjenoppbygget etter brann i 1872 - på middelalderske murer.
Middelalderkirkegården er i bruk. Ved registreringen i 2009 var det mer enn 10 gravleggelser fra tiden etter 1945. Sistegravlegging var da fra 1983.
Den gamle kirkegården ble noe utvidet i 1878, og før dette er tømmerkirken beskrevet å ha stått midt på kirkegården. Etter at tømmerkirken ble revet ble terrenget nivellert, og et stort antall lass grus ble påført kirkegården. I 1911 ble det opprettet hjelpekirkegård på Mundheim (Næss & Kolltveit 1981:355f).
Middelalderkirken var trolig en treskipet stavbygning, i 1665 beskrevet med svalgang rundt hele. Stavkirken ble i 1729 (1722-26 jf. Olafsen 1903:25 m/henvisning til Nicolaysen) erstattet av en tømmerkirke.