Området omkring Vindinge kirke var allerede i vikingetiden og den tidlige middelalder af stor betydning. En befæstet vold fra vikingetiden ved Rosilde skal muligvis ses i forbindelse med Gammelborg, der er en tilflugtsborg fra jernalderen, men som nyere arkæologiske udgravninger har vist muligvis også har været i brug i vikingetiden. Der er desuden fundet spor af sæsonhandelsplads, hvor Vindinge Kirke ligger i dag. Her er blandt andet fundet arabiske sølvmønter.
Ifølge Svend Aggesens krønike fra slutningen af 1100-tallet, blev Kong Svend Tveskæg sat i land ved Vindinge, efter han var blevet løskøbt fra fangenskab hos jomsvikingerne i Polen med sin vægt i guld. Især de danske kvinder havde bidraget med deres smykker, og som tak havde kongen givet dem arveret – dog måtte de kun arve halvt så meget som mænd.
Placeringen ved Vindinge Å, som er Fyns næstmest vandrige åsystem, har gjort tilgangen til området med skib meget nemmere i vikingetiden og tidlige middelalder. Den fungerede som herredsby, men i 1299 flyttede kongen herredstinget til Nyborg, der var blevet den vigtigste by på Østfyn. Vandstanden i åen sank nemlig betragteligt, da man ledte vandet fra Vindinge Å via Hjulby Sø indtil Nyborg Slot for at få vand i voldgravene omkring slottet og byen omkring år 1200 med slusen ved Kullerup.
I middelalderen blev der tilføjet to korsarme til kirken, formentlig først i nord (hvor Skt. Mads Kapel befinder sig) og så i syd. Endnu senere fik den sit anselige tårn, hvor der i dag er indgang, og et lille våbenhus op ad den søndre korsarm (i dag ligkapel). Kirken er rigt udstyret indvendig med en prægtig gylden fløjaltertavle fra ca. 1480 og der har været træskærerarbejder fra Claus Bergs berømte værksted i Odense i kapellet til Skt. Mads. Det hænger formentligt sammen med, at adelsslægten Ulfeldt, der sad på Holckenhavn, brugte kirken som begravelseskirke fra 1420-1616.