Trots namnet Ödeby var socken ingen avkrok i gamla tider, tvärt om. 1200-talets namn Öynum syftade på att kyrkan låg på en ö i sjön Väringen. Genom åren har det blivit Öya, Öynum, Öbo, Ödbo och från slutet av 1600-talet Ödeby.
Socknens läge vid Väringen och Arbogaån - en av landets viktigaste handelsleder under medeltiden - gjorde att stormannasläkterna i landet återfinns som ägare till marken här redan tidigt. Den viktigaste gården var Tuna, som senare blev Kägleholm. Ödeby kyrka var troligen en gårdskyrka som tillhörde Tuna och alltså inte en församlingskyrka.
Den ursprungliga stenkyrkan hade ett kvadratiskt torn, ett något bredare långhus och en vägg med öppning in till ett smalare kor. Under senmedeltiden breddades koret och väggen till långhuset togs bort. En sakristia anses ha funnits. Byggnadsmaterialet var huvudsakligen gråsten, det råmaterial som fanns i trakten. Långhuset hade troligen öppna takstolar utan innertak. På detta tyder kvarvarande rester av målade imitationer av tegel och vita fogar upptill i väggen mot tornet. Till våra dagar finns endast tornet och vapenhuset kvar från den första stenkyrkan, som förmodligen byggdes runt 1200. Den nämns i skrift först 1314.
Flera kända personer från historien har ägt mark på ön och därför också haft sk patronatsrätt till kyrkan, de har svarat för underhåll och tillsatt präster. Några av dem är Ulf Gudmarson av Ulfåsaätten och hans hustru Birgitta Birgersdotter - “den heliga Birgitta”, Sten Sture d.ä., Gustav Vasa, och när vi kommer till 1600-talets mitt, Magnus Gabriel del la Gardie.
Vid reformationen blev Ödeby en annexförsamling till Lillkyrka i Glanshammars pastorat.
Kyrkans nuvarande utseende kom till stånd genom Magnus Gabriel De la Gardies genomgripande restaurering 1679-80. Han följde stormaktstidens stil – barocken och ville skapa en kyrka värdig Kägleholms relativt nybyggda barockslott, som han låtit uppföra i direkt anslutning till kyrkan.
Kyrkan förlängdes genom ett tresidigt kor i öster. Sakristian lades norr om långhuset. En vacker sandstensportal togs upp på tornets västra gavel. En ingång, även den i sandsten, till kyrkan fick ny inramning på långhusets södra sida. Tornet försågs med en hög spira och fick ett tornur, som ursprungligen var avsett för rådhuset i Lidköping.
Invändigt skedde stora förändringar; en ny predikstol med försilvrade figurer – evangelister, dygder och bibliska personer tillkom, ett arbete av en konstsnickare med efternamnet Siptus. Golvet lades med grå och röda slipade kalkstensplattor. Många inventarier skänktes av de la Garide för att ge kyrkan ett vackert och påkostat inre. Till utsmyckningen hör bland annat en målad dörr föreställande översteprästen Aron, som nu hänger i vapenhuset.
Under 1700- och 1800-talen skedde reparationer och ett fåtal förändringar. Någon gång före 1754 måste tornspiran ha ersatts med den kopparklädda huven som finns idag. Tornuret togs troligen bort 1815.
På 1950-talet genomfördes en omfattande renovering och konservering av kyrkan med hjälp av en donation av dåvarande ägaren till Kägleholm, Nils Danielsen. Kyrkans yttre putsades och vitkalkades, portalerna rengjordes, yttertaket byttes ut mot kopparplåt och tornets kors förgylldes på nytt. En ny yttertrappa lades vid tornentrén. Kyrkans inre rengjordes från sot och vitkalkades,
bänkkvarteren fick tegelgolv och bänkarna, altarringen, predikstolen och läktarbarriären återfick färgsättningen från 1680
Altarskåpet är tillverkat i Mechelen i Flandern under tidigt 1500-tal och kompletterat under 1600-talet.
Kyrkan äger 22 målningar, de allra flesta skänkta av de la Gardie och hittagna, dels från Läckö och dels från Kägleholm. De två mest iögonfallande är två kopior av Albrecht Dürers “Adam och Eva”, utförda på de la Garides beställning från originalen, som då ägdes av drottning Kristina men som hon senare skänkte till spanska kungaparet och som nu finns i Pradomuseet. De hänger i sakristian. Inne i kyrkan sitter stora oljemålningar med bibliska motiv av både kända och okända 1600-talskonstnärer.
Orgelläktaren byggdes om 1855. Samtidigt installerades en ny orgel med åtta stämmor och en manual, byggd av E A Setterquist.