Den ældst kendte skole i sognet er Rytterskolen, der blev taget i brug omkring 1723.

Kongen, Frederik IV, bestemte i 1721, at der skulle bygges 241 nye skolebygninger i rytterdistrikterne. Alle skolerne skulle være ens. På Fyn skulle der bygges 20 af den slags skoler, der blev kaldt rytterskoler eller kongelige skoler. En af skolerne lå her i Paarup, omtrent hvor Solgårdsvej munder ud i Tarupvej. 

Ovenfor kan man se, hvordan skolen så ud. Der var kun skole i den ene halvdel af bygningen. Læreren boede i den anden halvdel. Oven over døren var der indmuret en tavle, på hvilken der stod, at kongen havde opført skolen.  I skolestuen kunne der være op til 44 børn. Alle børn fra 7 til 14 år blev undervist sammen, man blev altså ikke delt op i klasser. Lokalerne var mindre end de lokaler, der er på såvel Paarup som Tarup Skole. Der kan ikke have været rart en vinterdag, hvor børnene var gået gennem sneen til skole. De havde deres våde overtøj med ind i klassen, som kun kunne opvarmes af en kakkelovn. Stalden var lige inde ved siden af. Og væggen var ikke tæt. Der er ingen tvivl om, at der har været en skrækkelig lugt i klassen. I en indberetning fra 1856 får man indtryk af atmosfæren i klassen: mellem 40 og 50 elever i skolestuen, der ikke havde trækrude eller ventil til udluftning. Uden for lokalet var der tre latriner og en stald med tre køer. En del af lærerens løn kom fra landbruget, idet der til skolen hørte 6 tønder land. 

Ryttergodset blev solgt i 1760’erne, men der var fortsat skole i bygningen, og for eleverne var der sikkert ikke nogen forskel at mærke.

I 1869 blev en ny skole taget i brug ved kirken. Nu var der to klasselokaler, og der blev ansat en andenlærer, der fik bolig ovenover skolestuerne.

I 1940 byggedes gymnastiksal og et klasselokale, og der var skolekøkken og sløjdlokale i kælderen.

Til at aflaste Paarup Skole blev der i 1936 bygget en forskole i Villestofte. Her gik de yngste årgange.	Også Stegsted fik en forskole. Den havde i nogle år til huse i lejede lokaler på Stegstedgaard, men i 1939 flyttede den ind i egne lokaler.	På grund af det stigende elevtal blev kirkeskolen i 1963 udvidet med det, der nu kaldes Paarup Ny Skole, eller bare Paarup Skole. Samtidig blev forskolerne nedlagt. Der er bygget til og om på skolen adskillige gange siden.