Redan på 1200-talet lär en kyrka ha funnits i Malexander. Den första kända uppgiften om en kyrka är dock från 1345 då Birgitta Birgersdotters ingifte morbror Knut Jonsson som var ägare till den närbelägna Aspenäs gård testamenterade pengar till kyrkan och prästen Lambertus. Denna kyrka som var av trä eldhärjades 1587 och en ny träkyrka uppfördes på platsen. Sakristian som var av sten kan ha klarat branden och ingått i den nya träkyrkan. Under 1800-talet hade traktens befolkning blivit så talrik att kyrkan inte längre räckte till. 1877 påbörjades uppförandet av en stenkyrka alldeles söder om den gamla träkyrkan. 1881 var bygget slutfört enligt arkitekt Ernst Jacobssons ritningar och byggmästare Johan Sundqvist året efter revs träkyrkan. Man lät dock fotografera den innan den revs. Den nya kyrkan blev en rymlig kyrkobyggnad i medeltidsromantisk stil. Den bestod av ett rektangulärt långhus med ett halvrunt kor i öster med bakomliggande sakristia och torn i väster. Vintern 1929 uppstod en brand som förvandlade kyrkan till en svartbränd ruin. Eftersom murarna av den eldhärjade kyrkan var i gott skick kunde dessa användas vid återuppbyggnad av kyrkan. Arkitekt Johannes Dahl från Tranås svarande för ritningarna och som byggmästare anlitades Hjalmar Linder från Mjölby. 1931 var kyrkan färdig. Det som skilde kyrkans exteriör från den tidigare kyrkan var endast den höga spetsiga tornspiran. Interiören ändrades något. Långhusets västra del avdelades för sakristia och personalutrymme varvid kyrkorummets storlek blev förminskat. Koret frilades helt p.g.a. sakristians förflyttning.