I begyndelsen af 1100-tallet erstattedes Kirke Saabys oprindelige trækirke af en opført i sten. Denne kirke blev, som blandt andet Roskilde Domkirke, opført med tvillingetårne. I dag er de to tårne borte og tilbage står kun en synlig rest af det ene i våbenhuset på den nu værende kirke.
De sengotiske kalkmalerier i våbenhuset er kirkens yngste, og er fra begyndelsen af 1500-tallet. Det mest iøjnefaldende er et dommedagsbillede. Kristus sidder på en regnbue som verdens dommer. Maria og Johannes Døberen knæler ved siden af ham, mens de bedes for menneskeheden. Under dem myldrer de døde op af gravene.
I våbenhusets yderste mur sidder en sten med helleristninger som er 3000 år gamle.