Hur vet vi att kyrkan är 900 år? Är allt ett påhitt för att väcka uppmärksamhet? Det finns inga dokument från den tiden, men arkeologin ger nya möjligheter att bedöma åldern på träet i takstolen på kyrkan. En modern metod: ”dendrokronologisk undersökning” gör att vi kan veta att timret fälldes 1112 (med några års marginal åt båda hållen). Hur Östergötland såg ut på den tiden vet vi mycket litet om. Biskopen i Linköping är känd i dokumenten först 1120. Vad biskopen hette är inte känt. Det finns uppgifter om ett par biskopar, Henrik och Rikard. Någon av dem lär ha invigt kyrkan i Herrestad 1112. Biskop Kol har sedan, ungefär 75 år senare, bott i Herrestad och även byggt den första Kolsbro över Svälingeån. Nockstocken till takstolen i Herrestad är dock ännu äldre och tillhör kanske den träkyrka som borde ha föregått den kyrka vi nu har.
Även om det är en spännande utflykt i tiden att meditera över hur Herrestad såg ut när kyrkan byggdes är det viktigaste att den under 900 år varit socknens centrum. Kyrkan beskriver socknens historia in i vår tid. Gravstenarna i golvet, nattvardssilvret, altarskåpet, predikstolen, malmkronorna m.m. Från vår egen tid finns en orgel från R Kohlus orgelbyggeri i Vadstena.
Herrestad var under 1000-talet en stormannagård och en kungsgå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 från det medeltida 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.
Interiören förändrades vid 1400-talets början då tegelvalv slogs. Valven är putsade och dekorerade med blad- och bandornament i rött och svart. Bland inventarierrna kan nämnas en stol, från kyrkans första århundrade, avsedd för biskopen i Linköping som tidvis bodde i Herrestad. Orginalet är sålt till Statens Historiska Museum men en kopia finns i koret. I kyrkan finns flera medeltida skulpturer. Bland annat en Pietá, dvs jungfru Maria med den döde Kristus i sitt knä.
1100-tals-biskopen Kol är starkt förknippad med Herrestad. Han lät uppföra en bro, i flera spann, över Mjölnaån på gränsen mellan Herrestad och Strå. Kolsbro fanns kvar till 1840-talet då den byggdes om. Biskop Kols källare öster om kyrkan ligger på den plats där han en gång hade sin bostad.