Bygning
Vejlø kirke er en teglstensbygning fra o. 1275. Den bestod oprindelig af kor og skib, hvortil der o. 1500 blev føjet et tårn i vest og et sakristi (præsteværelse) ved korets nordside. Kirkens hoveddør er nu en portal i tårnets vestside, der leder ind til våbenhuset i tårnets nederste etage.I skibets langsider ses under de vestligste vinduer kirkens to gamle, nu tilmurede døre.

Foran norddøren har der tidligere været et våbenhus, vel fra o. 1500. Det er revet ned engang i 1800’erne, men man fandt husets fundamenter ved en arkæologisk udgravning 2002.

Af de smukke, murede hvælv er dét i koret samtidig med kirkens opførelse i 1200’erne, mens de to hvælv i skibet er indbygget senere, måske i 1400’erne. Korhvælvet smykkes af et kalkmaleri, der er lige så gammelt som kirken. Det forestiller den tronende Kristus i en ”mandorla”, omgivet af de fire evangelistsymboler, angivet med deres navne. Billedet har været overkalket, men er fremdraget igen 1872.

Kirkens store jernvinduer og portalen i vest er kommet til ved restaureringer i 1846 og i 1870’erne; oprindelige vinduer ses nu kun i korgavlen. Ydermurene var rødkalkede (ligesom Vester Egesborg kirke) indtil 1870’erne, da man rensede for puds og kalk, så facaderne igen fremtræder med deres store røde munkesten.

 
Inventar
Inventaret præges af den berømte billedskærer fra Næstved, Abel Schrøder, der har leveret både altertavle (1669), prædikestol og stolestader (1668) samt et præste-epitafium i korets sydside fra 1640’erne. De rige udskæringer er udført i den såkaldte bruskbarok, og de fine arbejder, der helt har fornyet kirkens inventar, er bestilt af kirkens patron, ejeren af Gavnø, Helle Rosenkrantz, der kort forinden (1667) havde mistet sin ægtefælle, admiral Niels Trolle. Deres adelsvåben, Trolle og Rosenkrantz, ses på altertavlen og prædikestolens lydhimmel og på stolegavlene, ledsaget af deres sammenskrevne initialer: H(elle) R(osen)K(rantz) og N(iels) T(rolle) sammen med et skibsanker.

Mest berømt er prædikestolens fantasifulde bærefigur, der forestiller et kvindeligt uhyre med dyrefjæs og kohale, og som populært bliver kaldt for ”slattenpatten” på grund af de hængende bryster, hvad der har affødt mange sagnagtige historier. Bærefiguren skal dog – som en tilsvarende under prædikestolen i Gavnø slotskapel – opfattes positivt som en mandlig trold, nemlig Trolleslægtens våbenfigur, der beskytter kirken. Forklaringen findes i en latinsk indskrift på selv prædikestolen, hvor der frit oversat til dansk står: ”Når Djævelen vil omstyrte kirkerne, så bæres de oppe af Trollernes våbentegn”.

Fra den katolske tid har kirken bevaret et fint alterskab, et nordtysk arbejde fra o. 1520. Her ses i midten apostelen Andreas og i sidefløjene relieffer med fire scener fra hans legende, bl.a. hans korsfæstelse på et ”Andreas-kors”. På fløjenes ydersider ser man, når skabet er lukket, malede figurer forestillende to ridder-helgener: Maritzius, karakteriseret som sort, og Sebastian, hvis nøgne bryst gennembores af pile. Se og Andreastavlen i Vejlø Kirke.

Den firkantede romanske døbefont, fra 1200’erne, er af skånsk sandsten. Den er som ti andre døbefonte på Sjælland indført fra Skåne og har en ”søster” i Vollerslev kirke, ligesom der også findes en helt tilsvarende i domkirkemuseet i Lund. Men fonten har kun været i Vejlø siden 1800’erne, og hvordan den er kommet hertil, vides ikke.

Kirken har to klokker. Den ældste er støbt af Olaf Bendtsen i 1506, altså endnu i den katolske tid. Den yngste – det er den, der høres morgen og aften og ved gudstjenester – er støbt i København 1836; men i sig indeholder den jernmalm fra en ældre klokke, støbt i 1551 af de lybækske klokke- og kanonstøber Karsten Middeldorf.

 
Kirkegården
Den gamle kirkegård omkring kirken blev 1886 afløst af en ny kirkegård ca. 200 m nordvest for kirken. Det skete for at skaffe plads til den voksende befolkning og gav samtidig Gavnø mulighed for at indrette en ny begravelsesplads for slægten Reedtz Thott. Tidligere blev medlemmer af slægten begravet på et gravsted lige øst for koret, hvor deres navne ses i gavlen. Her er også begravet naturforskeren og ”jordomsejleren” Morten Wormskjold, der døde på Gavnø 1845.

 
Kirkeejere
Vejlø kirke var ejet af de vekslende besiddere af Gavnø 1584-1963. Jernbogstaverne på tårnets nordside henviser til nogle af kirkeejerne, ”HL CL 1846” til Henrik Lindenov og Cidsel Lunge, ”ORT CAF 1846” til Otto Reedtz Thott og Caroline Amalie Føns.