Kyrkan byggdes under andra halvan av 1200-talet. Den är byggd i senromansk stil med ett rektangulärt långhus i öst västlig riktning med koret i öster och sakristian i norr. Mycket talar för att den ersatte en äldre kyrkobyggnad i trä. Bland annat genom att dopfunten är äldre än kyrkan samt ett dekorskuret hammarband i sakristian som också daterats till före den nuvarande kyrkans byggnad.
Den ursprungliga kyrkan var endast 15 meter lång och sträckte sig i väster till de nuvarande bakre fönstren. Bänkar fanns inte i det medeltida kyrkorummet, möjligen några sittplatser för de gamla längs någon av väggarna. Församlingen stod på jordgolvet medan mässan pågick i det dunkla rummet. Den enda ljuskällan var vaxljus. Fönstren var också av mindre storlek. Kyrkan hade ursprungligen två ingångar på söderväggen. Den mindre koringången är kvar med sin gamla järnbeslagna trädörr, som har kulhål från striden 1611.
En mindre tornbyggnad har i medeltid funnits för kyrkans klockor. Omkring år 1600 målades kyrkan invändigt med målningar av Växjö-målaren Johannes Petri Pictor. Dessa överkalkades dock senare, men ett parti över sakristians dörr är numera återställt.
Under åren 1750 till 1768 byggdes kyrkan till med fem meter åt väster. Läktaren byggdes och fönstren gjordes större. Målningar i tak och läktarbröst gjordes av Olof Rosenblad från Gränna. Draperimålningarna är gjorda av okänd konstnär. Predikstolen fick nu också sin nuvarande plats. Tornbyggnaden med de 2 medeltidsklockorna nermonterades och klockstapeln byggdes av Jon Arwidsson. Huvudingången flyttades från sydsidan till västsidan.
Nästa stora renovering gjordes 1870 då de två vapenhusen rivdes och ersattes av det nuvarande med rymligare läktare däröver. Kyrkans första orgel installerades. Nu fick kyrkan sitt nuvarande utseende med yttermåtten 20,8 meter gånger 9,1m plus vapenhus. Kyrkan rymmer nu 150 personer och vi är nära den tid då vi hade ett befolkningsmaximum i Ödestugu. 1890 var det som mest omkring 1100 personer i socknen.1905 slätputsades väggarna, detta pga den tidens modernare smakriktningar men också troligt pga jordbävningen föregående år som gjort att mycket puts lossnat. Vid denna renovering sattes ett korfönster in, tillverkat av Stockholms glasmästeri. Korfönstret plockades ner och är nu placerat på församlingshemmets fondvägg.
Under renoveringen -54 till –56 försökte man återställa den karaktär som var före 1870. Kyrkans yttertak av tegel ersattes 1966 med spåntak som sedan underhålls med tjära.
1992 installerades ett nytt uppvärmningssystem som bättre reglerar värme och fuktighet och är mer skonsamt mot kyrkans kulturskatter. Nu byggdes också handikapptoalettrum och förråd i vapenhuset. Det nuvarande korfönstret av glaskonstnären Ann Wolf sätts in.