Det är inte känt när Östra Eneby kyrka byggdes. Det finns inga bevarade dokument om saken och undersökningar av byggnaden har inte gett några entydiga besked. Ändå har i senare tid årtalet 1100 – på oklara grunder – skrivits med stora siffror på kyrktornet.
Antikvarien och konsthistorikern Åke Nisbeth ansåg att formen på den äldsta delen av kyrkan talar för en datering till tiden omkring 1200 eller 1200-talets början. De närmaste parallellerna hittade han på Vikbolandet, där bland annat kyrkorna i Furingstad och Tingstad har likartade planlösningar. Även kalkmålningarna i taket kan dateras till denna tid av stilistiska skäl.
Av en bevarad sångbok från början av 1500-talet framgår att Sankt Lars var kyrkans skyddshelgon. Socknens namn var ursprungligen Eneby, men på 1700-talet lades Östra till för att skilja den från (Västra) Eneby i Kinda.
Vid en restaurering 1955 hittades en runsten med två kors under golvet i koret. Den har daterats till 1000-talets mitt och tros ha tagits till kyrkan under medeltiden för att användas som altarskiva. I väggarna påträffades då också ett antal inmurade stenar med ornamentik som kan vara från tidigt 1100-tal.
Om stenarna kommer från en äldre stenkyrka på platsen är, enligt Nisbeth, svårt att avgöra. Liknande stenar finns i portaler i de tidigmedeltida kyrkorna i Vårdsberg, Örberga och Östra Skrukeby. Runstenen visar i alla fall att det redan vid 1000-talets mitt fanns kristna i bygden.
I slutet av 1300-talet gjordes den första större ombyggnaden av kyrkan. Det urspungliga koret revs och det nuvarande, bredare och längre, uppfördes. Samtidigt – eller mycket snart därefter – byggdes en stor sakristia vid korets norra vägg. Tegelvalv slogs i alla delar av kyrkan. Det ännu bevarade vapenhuset i söder kan vara samtida med koret eller några decennier yngre.
Kyrkan fick också ett torn – troligen redan under medeltiden. På en teckning från 1600-talet har kyrktornet en spira som bör ha tillkommit under 1500-talet eller något tidigare.
På 1600-talet byggdes vid korets södra vägg ett gravkor för adelsätten Schulman som ägde gårdarna Leonardsberg och Svärtinge i socknen. Koret omvandlades i början av 1900-talet om till dopkapell.
År 1719 härjade ryska trupper i Norrköping och på den omgivande landsbygden. De brände då bland annat Östra Eneby kyrka. Taket och tornhuven förstördes liksom all fast inredning, bland annat troligen ett senmedeltida altarskåp. Däremot kunde kyrksilvret räddas genom ett rådligt ingripande av församlingens kyrkoherde Erik Exing. Han är en av Östra Enebys mest kända präster och begravdes i kyrkan där hans porträtt ännu hänger. Erik Exing har även fått en gata vid kyrkan uppkallad efter sig.
När ryssarna dragit sig tillbaka inleddes återuppbyggnadsarbetet snabbt. Viktigast var att få kyrkan under tak och sedan skaffa ny inredning. Tornmurarna hade brandskadats så svårt att tornet revs och ersattes av en klockstapel. För att ge plats i kyrkan åt den växande befolkningen förlängdes långhuset åt väster där tornet stått.
År 1760 konstaterades att klockstapeln var i så dåligt skick att den inte skulle klara sig så länge till. Socknen började därför sätta av pengar till ett tornbygge och köra fram sten och virke. År 1773 kontrakterades en murmästare och två år senare var tornet klart. 1775 är därför det andra årtalet som i dag står högst uppe på tornet.
Under 1800-talet rensade en stor del av kyrkans äldre inventarier bort. Från medeltiden finns i dag bara en dopfunt och två höga ljusstavar. Dopfuntens fot är från 1100-talets slut och har tillskrivits den gotländske stenmästaren ”Majestatis”. Skålen är huggen i kolmårdsmarmor på 1200-talet. Ljusstavarna från slutet av 1400-talet, krönta med helgonfigurer, är kopior av de original som skänktes till Historiska museet.
Östra Eneby kyrka fick sitt nuvarande utseende genom en serie större renoveringar 1896, 1918 och 1954–1955. Vid den första höggs bågen mellan långhuset och koret till sin nuvarande bredd, 1918 frilades de medeltida kalkmålningarna och på 1950-talet tillkom nytt golv och nya bänkar.
År 2023 inleddes en utgrävning av Östra Eneby prästgård. Den låg några hundra meter väster om kyrkan och revs när E4 drogs förbi Norrköping. Där påträffades lämningar efter den medeltida prästgården med tillhörande trädgård. Bland fynden finns vackra importerade bägare och dekorerade knivskaft från 1500-talet.