Östra Herrestads kyrka är troligen från mitten av 1100-talet och uppförd i romansk till med långhus, kor och absid.
I portalen på södra långhusväggen kan vi i tympanonen kan läsa "Carl Stenmester scar thenna sten". Här får vi alltså namnet på denna kyrkas "arkitekt" Carl Stenmästare. Han var stenhuggare och kyrkobyggare på 1100-talet i Skåne, men bara här har han lämnat sin signatur. Stenhuggaren står bakom flera ornamenteringar i kyrkan, bland annat på kyrkans sockel runt hela byggnaden. Inne i kyrkan finns också två små pelare som huggits ut av Carl Stenmästare.
Den ursprungliga kyrkan hade troligtvis högt platt tak - härom vittnar rester av målningar uppe på det som idag är kyrkans vind. (Ovanför valven)
Under 1400talet slogs valv i kyrkan och senare samma århundrade försågs de med de kalkmålningar vi ser idag. Valven i kyrkan är rikt dekorerade med målningar föreställande människornas första tid med skapelseberättelsen, syndafallet och utdrivandet ur paradiset. I långhuset kan vi också se Marie kröning samt Yttersta domen. I koret och absiden finns en serie bilder ur Jesu liv och en nådastolsframställning där Gud Fader håller den korsfäste Kristus framför sig medan andens duva sitter på hans axel.På 1880-talen förlängdes kyrkan åt väster och nytt torn uppfördes.
Dopfunten från 1300-talet är i Älvdalsporfyr. På den finns fyra figurer i relief. En konung, en man på en drake, en man med bok och svärd och en man med gloria och korsstav.
Delar av kyrkans altaruppsats stammar från 1700-talet.
Man har funnit ett sigill med ett bomärke i form av ett kombinerat kors och ankare. Runt om bomärket finns en text som lyder: CLAMES CONVENTGH S (=Clemens församlings sigill). En äldre man som uppger sig ha fått det av sin fader, född 1797. Kanske kan sigillet ha hittats vid grundgrävning vid renovering av Gamla prästgården i Ö Herrestad (Skola år 1918).
