Præstemoseskolen er tegnet af arkitekt Hans Wilhardt og blev bygget i perioden fra 1955 til 1958.
Præstemoseskolen blev opført i tre byggeperioder. I 1955 blev første afsnit, som omfattede skolen for småbørn, taget i brug (i dag kaldet A-fløjen). I 1957 kom endnu en afdeling for større børn til (B-fløjen), og i 1958 kom den tredje afdeling med faglokaler og gymnastikfløj til (C-fløjen).
Skolen omfattede nu otte normalklasser for små børn og femten for store børn. Ud over dette var der også fem hjælpeklasser (datidens specialundervisning) og en lang række faglokaler samt særlige lokaler til børneplejestation, tandklinik og skolebibliotek. Til skolen hørte naturligvis også legeplads, boldbane, håndboldbane, løbebane og en springbane. Derudover var der opført en bolig til skolebetjenten (denne bygning bruges i dag af skolesundhedsplejen og skolens logopæd).
Den fuldt udbyggede skole stod færdig 11. august 1958, men den officielle indvielse fandt først sted 11. april 1959.
Ved indvielsen sagde skoleinspektør H. Svendsen bl.a.:
"Vi vil også prøve på at lære børnene, at det er nødvendigt at tage hensyn til hinanden, lære dem at vise respekt for andre mennesker, at man ikke hæmningsløst kan opføre sig, som man vil, men må tilpasse sig samværet med andre i klassen, i skolen og senere ude i samfundet"
I 1970’erne var skolen blevet for lille til at rumme alle distriktselever, og der blev bygget en midlertidig pavillon. I slutningen af 1970’erne var den gal med pladsen igen, og skolen blev i 1980 udvidet med D-fløjen, som den gang husede hjælpeskolen, indskoling og kontorer. I 2002 blev D-fløjens førstesal udvidet med yderligere 300 m². I 2024 overtog Præstemoseskolen bygningen ved skolens parkeringsplads, som hidtil havde huset kontorer for hjemmeplejen – dermed fik Præstemoseskolen en E-fløj.