El temple parroquial de Santa Maria de Palautordera és situat just a l’entrada del poble homònim, cap del municipi. Aquesta església apareix documentada ja l’any 862, en un precepte de Carles el Calb, on dóna al comte Sunyer I d’Empúries-Rosselló aquesta parròquia junt amb la de Sant Esteve de Palautordera i Sant Esteve de la Costa, tal i com les havia cedit el 858 a Unifred o Humfrid en nomenar-lo comte de Barcelona i marquès de Gòtia. Aquest document és important també perquè s’hi marquen els límits d’aquest gran alou reial, i diu que se n’exceptuen els béns situats a Campins i al Vilaret de Cerdans, ja que les terres havien estat posades en cultiu per homes “hispani”. Això indica que el Montseny era terra de domini reial, i per això el monarca ho reparteix entre els seus nobles.
Aquests comtes devien vendre-ho a Trasovad, ja que l’any 908 trobem un document on aquest ven al comte de Barcelona, Guifré Borrell, allò que té “ in locum Vallense, valle que vocant Tordaria, vil·la Bitaminia, que vocant Palaciu, cum ecclesias, id est S. Marie virginis et S. Stephani protomartiris, et alia ecclesia que vocant similitar S. Stephani, qui est inlatere Montisigni ”. Poc després, aquesta propietat va ser cedida al monestir de Sant Cugat del Vallès, tal i com consta en un document del 986 on Lotari confirma a Odó, abat del cenobi, la vila Vidamenia, anomenada Palatium, a la vall Dordaria, i les esglésies de Santa Maria i Sant Esteve, amb els seus delmes, primícies i tributs; tal com ho dóna el comte Godfred per l’ànima del seu germà Sunyer.
En tots aquests documents es parla de la vila Vidamenia, que també s’anomena Palau, fet que fa pensar en la possible existència d’un Palaus o Palatio d’època romana. Aquesta hipòtesi, però, no ha estat confirmada ni documentalment ni arqueològicament; si bé es creu que l’actual església de Santa Maria va ser edificada sobre aquest antic palau.
El monestir de Sant Cugat tenia nombrosos béns i possessions a Palautordera, i l’abat n’era el senyor dominical, mentre que el dret jurisdiccional era del senyor del castell de Montclús. Aquest cenobi, el 1173, va projectar fer una divisió administrativa del seu patrimoni, que es va materialitzar entre els anys 1211 i 1216 amb la creació de quatre pabordies, una de les quals era la de Palau o Palautordera.
L’església era de col·lació del bisbe de Barcelona, però l’abat de Sant Cugat tenia el dret de presentació.
Referències concretes de l’església de Santa Maria es tornen a trobar en dos testaments: el de Guillem el 1035 i el d’Ovasi el 1046, jurats sobre l’altar de Santa Maria, a Palautordera. Des del segle XII ja hi ha referències a la sagrera d’aquesta església, on existia un nucli de població, però no tenim dades concretes fins al final del segle XV, que sabem que hi havia unes 30 cases.
En les visites pastorals del segle XIV es diu que tenia com a sufragània la capella de Santa Eulàlia de Tapioles, que sembla que havia estat església parroquial. El 1358, el rector de Palautordera reclama els beneficis d’aquesta església de Tapioles, ja que a causa de la pesta s’havia quedat sense parroquians.
La primitiva església romànica esdevingué insuficient i a mitjan segle XVI s’iniciaren les obres d’engrandiment. El 10 de juny de 1560, el vicari general va donar llicència per a engrandir l’església, que va ser beneïda el 1588. D’aquestes reformes resultà un edifici de característiques gòtiques, que va ser ampliat amb l’annexió de capelles laterals en els segles següents.
L’únic vestigi que tenim de l’època medieval és el primer cos del campanar, de base circular, construït amb palets, que fa pensar en una possible torre militar.