Det finns väldigt knapphändiga uppgifter framtagna om Nässja kyrkas byggnadshistoria. Kyrkan är genom dendrokronologisk provtagning, d v s årsringsanalys, daterad till 1100-talets andra hälft. Kyrkans medeltida takstol är till stora delar bevarad och på Historiska museet i Stockholm finns sedan 1906 en ornerad bräda från den romanska takkonstruktionen. Kyrkan uppfördes av kalksten och gråsten med ett rektangulärt långhus och smalare absidkor. Senare under medeltiden valvslogs kyrkorummet och sakristian tillbyggdes vid korets nordvägg. Kyrkans exteriöra utseende under 1600-talet är känt tack vare en teckning, utförd 1669 av tecknaren och fornforskaren Elias Brenner. Avbildningen visar kyrkan från sydöst med ett stort putsat vapenhus i söder, vilket i öster är sammanbyggt med en lägre byggnad med pulpettak och något som kan tolkas som liggande panel. Över långhusets västra del reser sig en takryttare. År 1695 nybyggdes eller ombyggdes takryttaren och klockorna uppges ha flyttats dit från en fallfärdig klockstapel. Några större förändringar av kyrkans exteriör skedde sannolikt inte under 1700-talet, vilket framgår av en teckning från 1807. Teckningen, som är gjord av Johan Fredrik Kock, visar att den lilla tillbyggnaden, som eventuellt kan ha varit ett benhus, har rivits. Takryttaren, som nu är inklädd med spån, har eventuellt försetts med en högre spira. Teckningen visar även att kyrkan hade en smal korportal och ett litet högt placerat fönster öster om porten. Även interiören förnyades. En medeltida altartavla ommålades 1701 och 1785 tillkom en ny predikstol. Altartavlan kom enligt Carl Fredrik Broocmans beskrivning över Östergötland från Vadstena klosterkyrka ”Altartaflan har under påwetiden stådt i Wadstena Kloster-kyrka, hwarifrån hon är hitförärad; och föreställer uti slät målning Herrans Nattwards Instiftelse.” Under 1800-talets första hälft, eventuellt 1816, skedde en omfattande ombyggnad. Vapenhuset på södra sidan revs och sydportalen murades igen. En ny portal togs upp på västra gaveln och ett nytt vapenhus av trä uppfördes. Genom Broccmans beskrivning från 1760 vet vi hur kyrkan såg ut före förändringarna; ”Inuti är hon af fine hwalf nog låg och tämmeligen mörk; hwartil then gamla påwiske målningen, som ännu är i behåll under hwalfwen, mycket bidrager: och kunde hon ansenligen uplysas, om hwalfwen hwitmenades.” De bemålade medeltida valven revs och ersattes av ett plant trätak och kormurarna höjdes och kyrkan fick ett gemensamt yttertak över kor och långhus, vilket ger kyrkan ett mycket karakteristiskt utseende. År 1856 försågs kyrkan med en orgel, som inköptes från orgelbyggarna Nordström i Flisby. Den har en osäker datering, men är sannolikt äldre än 1856.