Kastrup Kirke blev opført i rundbuestil - den såkaldte romanske stil. Vinduerne var små. Større vinduer ville give for meget træk, da man dengang ikke havde glas. Kirkens bygningshistorie er typisk for det store flertal af vore landsbykirker. I den tidlige middelalder blev skibet og koret bygget, og i slutningen af middelalderen blev koret ombygget, og tårn, våbenhus og sakristi føjedes til.

Allerede i 1250 oplevede man en ny byggestil i Danmark, gotikken - den såkaldte spidsbuestil. Og nu ønskede man sig også i Kastrup store luftige og lyse kirkerum. Det betød, at Kastrup Kirkes tagkonstruktion blev revet ned for at give plads til de nye hvælvinger. Hvælvene og skibets forhøjelse er foretaget o. 1500 og er i sengotisk stil.

Kirken var fra 1555 til 1856 annekskirke til Vordingborg, og den første sognepræst blev Ludvig Edvard Lakier fra 1856. Ved ryttergodsets bortsalg i 1774 kom Kastrup Kirke ind under hovedgården Rosenfeldt og var i dennes eje indtil 1960.