I både Gårdveda och Målilla var de första kyrkorna byggda i trä. De omtalas under 1500-talet men deras exakta ålder är okänd. Målilla kyrka brändes i samband med nordiska 7-års kriget 1567. Den nya träkyrkan rönte samma öde under Kalmarkriget 1611. Den träkyrka som stod klar 1614 stod kvar till dagens stenkyrka uppfördes 1822. Troligen hade även Gårdveda kyrka byggts om men när detta gjordes är inte känt.
Vid en biskopsvisitation 1768 dömdes de båda träkyrkorna ut och församlingarna uppmanades att bygga nytt. Eftersom avståndet mellan de båda kyrkplatserna var litet skulle man bygga en ny gemensam kyrka. Beslutet hade knappt fattats förrän sockenborna i Gårdveda ångrade sig och ville bygga egen kyrka. Tvisten löstes år 1800 genom att de båda socknarna slogs samman. Nu inleddes arbete med att ta fram ritningar till en ny kyrka som skulle byggas i Målilla. Detta arbete skulle dra ut på tiden. Under den tid planeringsarbetet pågick framlades förslag om såväl rundkyrka som hexagonal kyrka. Socknens ekonomi och svårigheten att på tag i en byggmästare som vågade sig på en del av projekten gjorde dock att den kyrka som slutligen uppfördes fick en traditionell plan med torn i väster och sakristia i öster. En bidragande orsak var också förutsättningarna på platsen. Kyrkan skulle byggas på en plats strax öster om den gamla träkyrkan, nära landsvägen. De slutliga ritningarna gjordes av arkitekt Per Wilhelm Palmroth vid överintendentsämbetet. År 1820 påbörjades arbetet och två år senare stod byggnaden klar. Arbetet leddes av stiftsbyggmästare Johan Holmberg, Linköping. Kyrkan invigdes 1824 av biskop Marcus Wallenberg.
Arkitekt Palmroth ritade vid den här tiden flera kyrkor runt om i landet. I Kalmar län är han upphovsman till Fliseryds kyrka som stod klar 1818. I Fliseryd blandas nyklassicism med tydliga nygotiska inslag. Målilla är en för tiden typisk nyklassicistisk kyrkobyggnad. Liknande finns t.ex. i Rumskulla och Mörlunda. Samtliga dessa tre kyrkor har en historiserande stildetalj i form av de palladianskt utformade ljudluckorna. Även interiört domineras Målilla kyrka av de nyklassicistiska stildragen men här finns även modernare tillägg.
Från Målilla gamla kyrka överfördes två epitafier över Gustaf Drake af Hagelsrum, död 1684, och Carl von Bruses, död 1730. Altartavlan och predikstolen bevarades i kyrkan men kom inte till användning. Altartavlan, skulpterat och bemålat trä från 1725, hade skänktes till kyrkan av överstelöjtnanten Johan Pilefelt och hans maka. På fotografier från 1918 kan man se att den placerats i kyrkorummet, på korets södra vägg, där den hänger än idag. Predikstolen hade tillverkats av bildhuggaren Jonas Berggren som var bosatt i Målilla 1745-1800. Den står idag på sakristians vind. I samband med planerna på att börja använda den på nytt konserverades predikstolen 1937 av konservator Sundbaum, Linköping. Den kom dock inte att tas i bruk på nytt. I tornet hängdes de båda klockorna från Målilla kyrka och storklockan från Gårdveda. Lillklockan från Gårdveda såldes till Persnäs församling på Öland. Klockorna var gjutna på 1600-talet. 1839 göts klockorna om av J. G. Liljedahl, Stockholm, till en storklocka och en lillklocka. Storklockan har omgjutits ytterligare en gång 1930 av M & O Ohlsson, Ystad. Lillklockan ersattes 1977 av en ny klocka från Ohlssons Klockgjuteri, Ystad.
Bland de inventarier som nytillverkades fanns altarringen. Uppgifter om den slutna altarringens dekorativa måleri har länge saknats men experter anser idag att de utfördes av Pehr Hörberg, en av tidens mer kända kyrkokonstnärer. Bilderna är utförda i grisailleteknik. Motiven anses vara präglade av konstnärens pietistiska trosuppfattning. Förebilderna är troligen holländska.
År 1848 var kyrkans orgel klar. Verket tillverkades av f. rustmästaren vid Jönköpings regemente Sven Nordström. Han tillhörde den s.k. Solbergaskolan som hade rötterna i svenskt 1700-talsorgelbyggeri. Nordström räknas som en av de främsta bygdeorgelbyggarna i landet och orgeln i Målilla anses vara ett mycket fint arbete. Orgeln har renoverats 1962 av Bernhard Svensson, Oskarshamn, och 1986-87 av A. Magnussons Orgelbyggeri, Mölnlycke. Dess fasad ritades av C. G. Blom-Carlsson 1847.
Den nya predikstol som tillverkats för kyrkan var en altarpredikstol. Arkiteket Palmroth hade motsatt sig detta men fått ge vika för sockenbornas önskemål. Denna visade sig snart medföra akustiska problem. Därför byggdes 1850 en mindre, tillfällig predikstol på norra väggen. Det fanns planer på att installera predikstolen från Målilla gamla kyrka men när hela altaret omgestaltades i samband med renoveringen 1953 valde man att istället flytta altarpredikstolen till den plats den har idag och förse den med en ny trappa.
Den första stora kända renoveringen av kyrkan genomfördes 1913 under ledning av byggmästare C. J. Rolander, Kleveshult. Exteriört lades spåntaket om, takstolarna förstärktes, nya fönster sattes in och fasaden avfärgades i vitt. Fasaden ska tidigare ha varit avfärgad i en gulröd nyans med vita omfattningar. Interiört byggdes en ny bänkinredning som reducerade antalet platser med ca ¼. Koret och fönsternischerna försågs med dekormåleri. Det sägs också att äldre inredning renoverades men vilka inventarier det gällde och vad som gjordes sägs inte. Nya underhållsåtgärder på kyrkans exteriör genomfördes 1927. Då tjärades spåntaket, snickerier sågs över, taklisten liksom stenfoten lagades. Stenfotens kalkbruk knackades bort och ersattes med cement.
År 1937 installerades lågtrycksångvärmesystem i kyrkan efter ritningar av firma Albin Svenssons konstruktionsbyrå, Stockholm. Tre år senare, mitt under andra världskriget, fick kyrkan provisorisk elektrisk belysning installerat av Målilla elektriska byrå. Anledningen sägs ha varit bristen på stearinljus. År 1947 installerades fasta elinstallationer efter ritningar av Tor Engström, Ingenjörsbyrån för Elektronik. I början av 1940-talet knöts arkitekten Evert Milles till Målilla. Han kom att leda renoveringsarbetena i kyrkan under 1940- och 50-talen. Hans första bidrag var den dopfunt som skänktes av Föreningen kyrkans prydnad. Arkitekt Milles gjorde ritningarna, Axel Wallenberg modellerade och stenhuggaren Folke Samuelsson, Västervik, tillverkade den. Den gamla dopfunten av trä förvaras idag på sakristians vind. År 1949 byggdes lanterninen om och ett tornur installerades. Detta hade donerats av distriktsveterinär Axel Wallin. Samtidigt byttes tornets spåntak mot kopparplåt. Arkitekt Milles gjorde också ritningarna för den nya altaruppsatsen. Arbetet påbörjades 1943. Utförandet blev en kompromiss mellan Milles önskemål om en relief i trä och brons av Axel Wallenberg och Einar Forseths altartavla som beställts av Föreningen Kyrkans vänner. Arbetet genomfördes först 1953 i samband med den större renovering av kyrkorummet som arkitekt Milles ledde. Kyrkans vind isolerades med mineralull. Det förefaller också som om innertaket putsades och målades. Det finns uppgifter som tyder på att man också renoverade kyrkans golv. Byggnadsstyrelsen har uttalat sig om att man ser det som önskvärt att man skulle behålla trägolvet synligt i koret och gångarna. Troligen var det vid den här tiden som den södra trappan i vapenhuset togs bort. Två bänkrader längst fram i kyrkan togs bort. Korbänkarna utökades med två rader, en på var sida om altaret. Einar Forseths monumentala altarmålning, 7 meter hög, kom att bli utgångspunkten för kyrkorummets nya färgsättning i grått, ockra, vitt och svagt blått. Axel Wallenbergs relief placerades som en predella på altaret. Grisaillemåleriet från 1820-talet togs fram i koret liksom de perspektivistiskt ställda kolonnerna. Måleriet påträffades under renoveringsarbetet. I samband med renoveringen konserverades altarringen, gamla altartavlan, predikstolen och epitafierna av konservator Bertil Bengtsson, Linköping. Kyrkan återinvigdes av biskop Torsten Ysander.
Taket på långhuset byttes 1958 från spån till kopparplåt. Ombyggnaden av lanterninen och bytet av takmaterial är de största förändringar av kyrkans exteriör som gjorts. Koppartaket lagades första gången 1976 av Karl Nilssons plåtslageri, Målilla. Vid samma tillfälle sågs också fasadputsen över. I korets sydvästra hörn installerades 1982 en kororgel av Robert Gustavssons Orgelbyggeri AB, Härnösand. Året därpå flyttade familjen Drakes gravhäll från kyrkogården in i vapenhuset. Där hängdes det upp på den södra väggen.
Renoveringen av orgeln 1986-87 fick oanade konsekvenser. Några veckor efter invigningen av orgeln lossnade delar av innertakets puts. Vid en närmare undersökning visade det sig att takputsen var full av sprickor. Taket var naturligtvis gammalt men man misstänkte att skadorna drastiskt förvärrades i samband med invigningen av orgel då instrumentet verkligen hade använts fullt ut. Det ledde till att en planerad renovering av kyrkans interiör tidigarelades. Ritningarna till renoveringen gjordes av arkitekt Lennart Arfwidsson, Atrio Arkitekter, Västervik. Det putsade innertaket byttes mot ett trätunnvalv som målades i ljust blått. En läktarunderbyggnad som rymmer samlingsrum, toalett, städrum m.m. byggdes liksom en ny trappa till läktaren. På läktaren togs gradänger och bänkar på den norra sidan bort liksom en korbänk på var sida om koret. Trägolvet i koret och långhuset slipades och gesimsen i koret återställdes. Ett nytt fristående altarbord byggdes och Axel Wallenbergs relief sattes upp på väggen under altartavlan. Inredningen målades i en ny ljusare färgsättning i vitt, ljust gult, grått och engelskt rött. Ingången i väster handikappanpassades. Värmesystem och elledningar sågs över. Altartavlan konserverades liksom altarringen och övriga inventarier. Arbetet utfördes av konservator Jörgen Bengtsson, Östergötlands läns museum. Altartavlan fick en ny omfattning i form av en guldlist. Kyrkan återinvigdes 1989 av biskop Martin Lönnebo.
Under 1990-talet har kyrkans fasad renoverats vid två tillfällen. 1991-92 förgylldes kors och kula, tornets tak sågs över och snickerier målades. Man rengjorde och avfärgade också fasaden. 1997-98 blästrades fasaden och putsades. Spritputsade ytor avfärgades i en svagt gulröd nyans medan slätputsade partier avfärgades i vitt. Denna färgsättning av exteriören anses vara den ursprungliga. Arbetet utfördes av AB Karlssons Fasadrenovering, Ädelfors. År 1999 installerades bergvärme i kyrkan.