Herrestads kyrka har genom dendrokronologisk undersökning daterats så att timret i takstolarna fälldes 1112 (med några års marginal åt båda hållen). Herrestad var under 1000-talet en stormannagård. Här fanns sannolikt en kyrka av trä. 1112 ersattes träkyrkan av den ännu bevarade stenkyrkan. Därmed är Herrestads kyrka den äldsta daterade kyrkan i Sverige. Kyrkans äldsta delar är långhuset med kor och absid i öster. Tornet från 1100-talets slut byggdes i etapper. Sakristian tillkom under 1300-talet. Vapenhuset utanför sydportalen revs 1829. Portalen murades igen och ersattes av ett fönster. Nytt vapenhus inreddes istället i tornets bottenvåning. Ett prov från den profilerade takåsen visar en helt avvikande ålder från övriga träprover. Ursprungsträdet har nämligen börjat växa redan omkring år 867 och dess avverkning beräknas ha ägt rum vid mitten av tiohundratalet. Denna gamla ekstock är skulpterad men har inte så bra passform, varför man måste anta att den ursprungligen har formats för ett annat tak. Det ligger då nära till hands att misstänka, att den härstammar från en tidigare stavkyrka på platsen, som revs då stenkyrkan uppfördes. Vid den här tiden hörde Herrestad till den Stenkilska ätten och man byggde en kungskyrka med empor. Till att börja med bestod den nya stenkyrkan av långhus med kor och absid i öster. Byggnaderna täcktes av sadeltak belagda med tjärade träspån. Smala ingångar fanns både från söder och norr och högt upp under takfoten satt små fönstergluggar utan glas. Invändigt var kyrkan till en början oputsad och takstolarna synliga; remstycken och takås var sirligt ornerade. Mot slutet av 1100-talet tillkom ett kraftigt torn i väster. Hela tornet byggdes inte på en gång, utan övre delen uppfördes några decennier senare. Så småningom erhöll kyrkan ett innertak av trä, som kanske också försågs med målningar. I början av 1400-talet slogs tegelvalv i hela kyrkan. År 1716 inköptes ett orgelverk från Västra Tollstads kyrka för 150 daler. 1784 ville biskop och domkapitel riva kyrkan och uppmanade församlingen att bygga en ny tillsammans med Källstads församling. Det blev emellertid protester från sockenstämman, som lovade att kyrkan skulle repareras, vilket också gjordes 1797. År 1805 togs norra läktaren, för torpare och drängar, bort och 1829 flyttades den södra ingången till västsidan. Det södra vapenhuset med kakaltaret revs och tornets bottenvåning, som tidigare varit sockenmagasin, inreddes till vapenhus. Genom att sydportalen murades igen, blev det plats för ytterligare tvenne bänkar i den trånga kyrkan.