Den anselige stenkirke, som vi ser i Gudme i dag, har sandsynligvis haft en eller flere forgængere af træ.

Det er vanskeligt at datere den nuværende kirke. Sammenligner man med andre kirker på Fyn, kommer man frem til det resultat, at Gudme Kirke sandsynligvis er fra ca. år 1300.

Af den oprindelige stenkirke i romantisk stil er kun skibet bevaret i dag. Det er bygget af utilhuggede kampesten. Vinduerne har været små, og de sad helt oppe ved taget. Loftet har været et fladt bjælkeloft. Koret har også været opført af utilhugne kampesten, men mindre end det, vi kender i dag.

Omkring år 1400 blev mange fynske kirker bygget om - blandt dem Gudme Kirke. Det lille romantiske kor blev revet ned og bygget op i samme bredde som skibet. Materialerne var dels kamp, dels tegl. Østgavlen blev bygget af teglsten; resten af koret af kampesten. Teglsten anvendtes også til indfatningen om de nye større vinduer, som alle blev fladbuede (senere ændret til spidse buer; kun et fladbuet vindue er bevaret i kirken). Indgangsdøren mod nord ("herskabsindgangen") blev ligeledes fladbuet. I dag kan man på ydermuren tydeligt se, hvor døren var placeret. Også de oprindelige vinduer træder klart frem, når man udefra ser på kirkens nordvæg. Murene bygges endvidere højere, og loftet blev forsynet med hvælv til erstatning for det flade bjælkeloft. Hvælv og vægge blev prydet med kalkmalerier.

Udvendig blev kirken også præget af den gotiske byggestil.
Korets østgavl blev forsynet med kamtakker, tandskifte og et blændet vindue.
Tårnet blev bygget til kirken omkring år 1500 i sengotisk stil. Det har tidligere været meget højere, end det er nu, og det havde kamtakker i gotisk stil.

Et våbenhus blev bygget på sydsiden af skibet i 1603. Gavlen blev bygget med kamtakker, som er bevaret i dag. Fra 1603 og op til 1877 har der været indgang til kirkerummet via våbenhuset. I dag bruges våbenhuset til ligkapel.

I slutningen af 1600-tallet blev der indrettet en krypt under koret. Her er ejere af Broholm Gods og deres børn begravet i  tidsrummet 1690-1811.
Caspar von Wessel, bror til den berømte søhelt Tordenskjold, giftede sig i 1747 med enkefru Elisabeth Scheel fra Broholm og blev siden stedt til hvile ved hendes side i krypten i Gudme Kirke. Endnu i dag kan man finde Caspar von Wessels kiste, hans hustrus og flere andre kister. I 1878 blev kisterne restaurerede, siden har tidens tand sat sine spor på dem.

I begyndelsen af 1800-tallet var tårnet i en så elendig forfatning, at man besluttede at rive det øverste, mest brøstfældige ned og forsyne tårnet med fladt pyramidetag. Dermed forsvandt også de gotiske trappegavle. Ombygningen fandt sted 1836 ifølge årstallet på tårnets vejrhane.

Fra biskop Madsens visitatsbog ved vi lidt mere om kirken, end man kan læse ud fra skiftende tiders om- og tilbygninger af kirken.

Biskop Madsen skriver 1589 om Gudme Kirke:
 " Kirken tornet, taget met Holsten alt oc affset. Et Storkrede paa Enden. Wabenhusz ingen; de gaar ind aff wester Ende y Tornet; der ligger Præstens Halm ved den ene Side oc er nogre løse Fjele; ingen Huelling. I Dør paa Nordside neden for Choret. 5 Huellinger. Alteret den korsfæstede som i Gudbjerg. 1 Træ på Alteret at sette Lius paa. Prædikestolen offuer for Choret (Traller for Choret): er en neder i Kerken, Skarn, Her Henrik clager, den anden er hannem for høj for hans Hoffuid. Fonten i Choret..."

Efter svenskekrigene var mange kirker i miserabel stand. I en indberetning af 1664 til biskop Niels Bang meddeles der om Gudme Kirke, at den største klokke var sprukken og ubrugelig, tårnet forfaldent, klokkeværkets tømmer meget medtaget, kirkens tag manglede sten og kalk, det regnede gennem hvælvingerne, våbenhuset forfaldent og kirkedøren itu, kirkegårds muren manglede sten og kalk, kirkeporten itu og ubrugelig, vinflasken borte. Ja, kirken var åbenbart temmelig misligholdt og forfalden.

Gudme Kirke fremtræder i dag som en stor, rigt udstyret landsbykirke. Det, der især karakteriserer Gudme Kirke, er imidlertid de mange særprægede kalkmalerier, som sidst blev restaureret i årene 1980-82. Årstallet 1448 der er malet over korbuen, angiver kalkmaleriernes alder.

Fra reformationstiden og frem til 1877 har de gamle kalkmalerier været overkalkede. Ved en tilfældig afstødning af hvidtekalken viste der sig en indskrift over indgangsdøren fra tårnet, og man gik sp i gang med at banke al hvidtekalken af.

Kalkmalerierne har allerede på det tidspunkt været bedst bevarede på hvælvingerne, i skibets vest- og østende samt på korets vestvæg, og i dag er ethvert spor af kalkmalerier på væggene i skibet fjernet (bortset fra indvielseskorsene og paneldekorationerne).

I korhvælvingen er malet blomster- frugtopsatse. På vestvæggen i koret ses endvidere et korsegangssceneri : Kristus bærende på sit kors; i baggrunden tårne og mure, der må forestille Jerusalem.

Skibets hvælvinger er dekorerede med rosetter, flettede kors, sole, bomærker og initialer, ledsaget af rankeslyng og siksakbånd. I den tredie hvælving fra øst finder man et par træsko, som har givet maleren navnet træskomalerem. Tilsvarende træsko kendes fra andre af egnens kirker.

Korbuen og hvælvingen mod øst er bl.a. udsmykket med en enhjørning, et "AVE MARIA", et kors omslynget af træ med rødder, et lille tårn, en ridder med fjerbaret og skæg, mærker og bogstaver og også her sole og flere kors.

På skibets vestvæg er der et stort maleri. Vi ser en borg med omgivende mure og vindebro. Midt i denne borg har vi den skæggede borgherre med sin frue ved sin side. På den modsatte side af den spidse dørbue en drage, der med rejst kam hæver sit gabende svælg imod borgen. Dragen symboliserer ondskaben, der truer mennesker. Men kirkens hellige fred er lyst over borgen: "Pax huic domui et omnibus bitantibus (egl. habitantibus) in ea", som direkte oversat betyder, at der er fred over dette hus og alle dem, som bor i det.

Vender vi blikket fra kalkmalerierne til inventaret i kirken, kan man i koret se en særdeles velbevaret gotisk fløjaltertavle fra 1400-tallets sidste del. I midterskabet korsfæstelsen, i fløjene scener fra lidelseshistorien. På alterbordet er der store malmlysestager fra ca. 1750. På kirken alterbord er der under gudstjenester placeret et krucifiksur fra begyndelsen af 1600-tallet. Uret har stået i kirken fra midten af forrige århundrede, hvor det blev købt i Paris og til 1905 og igen fra 1982. Krucifiksuret er skænket af Broholm Gods.

Altertæppet er fremstillet lokalt i 1986. I vinduesnichen bag alteret er ophængt et lille højgotisk krucifiks. Ved alteret står der to smukke sengotiske korstole, sikkert fra Claus Bergs værksted. I koret findes der desuden et stort sengotisk egetræsskab og fire gravfaner og en blodfane.

I skibet er der en romansk døbefont af granit med glat, ægformet kumme. Dåbsfadet er sydtysk og fra 1500-tallets slutning. På skibets nordvæg hænger der seks små barokfigurer med Kristi våben. Figurerne har siddet på prædikestolens fyldninger indtil restaureringen i 1938-39, hvor de blev flyttet til nordvæggen. Ligeledes på nordvæggen hænger der en slægtstavle fra 1693 med Bille-slægtens stamtræ og våbenskjolde. Bille-slægten føres her tilbage til den sagnagtige stamfader Thørne Bilde til Allinge, der døde i 781. Tavlen er formentlig udført af Odensemaleren Christian Zachariassen Getruer. Over korbuen ses et sengotisk krucifiks. Prædikestolen er i 1675 skænket af Jørgen Skeel og hans hustru, Lisbeth Bille, fra Broholm. Deres våbenskjolde ses indvendig i prædikestolen. Den store messinglysekrone er fra 1682 og er ligeledes en gave fra Broholm. Den ene af de små lysekroner er skænket af venner af familie Sehested til minde om kammerherreinde Alexandra Sehested, der døde i 1903. På skibets sydside er ophængt et større epitafium over præsten Niels Madsen Lørup, der var præst i Gudme og Brudager i 20 år. Han døde i 1679. Orglet i kirken er bygget af P. Bruhn og Søn, Rødekro i Sønderjylland. Det er tegnet af arkitekt Ebbe Lehn Petersen og har 11 stemmer, 2 manualer og pedaler. Orglet stod færdigt i begyndelsen af 1988.

Den lokale husflidforening markerede sit 90-års jubilæum ved at udarbejde en præstetavle, som i 1983 blev ophængt på nordvæggen i våbenhuset. Spejl og stumtjener er også af nyere dato, nemlig fra 1986. Inden vi forlader kirke er det i midlertid nok værd at kaste et undersøgende blik på den bjælke, som hænger på vestvæggen i tårnrummet. På bjælken er der nemlig udskåret en mandshoved med tartarskæg, som minder om de ældste romanske stenhoveder f.eks. fra Tømmerby Kirke og også godt kunne være fra en norsk stavkirke. Har vi her en rest fra den stavkirke, som omkring år 1300 blev afløst af kampestenskirken ?

Gudme Kirke har 2 klokker.
Den største (ø 1095 mm) er fra 1737, fremstillet af Johan Barthold Holtzmann
den anden (ø 810 mm) er fra 1795, fremstillet af Daniel Conrad Herbst.