Tot i que el lloc de Palau és esmentat en la documentació medieval a partir dels segles IX-X, l’església no apareix escripturada fins al segle XII, concretament l’any 1100, quan un personatge dit Rosselló feu donació al capítol d’Elna de les vinyes que tenia a la “parrochia Sanete Mariae de Palad”, abans de peregrinar a Terra Santa. Poc després, l’any 1136 hom té notícia d’una transacció entre Riambau, canonge d’Elna, i Arnau de la Tor sobre la successió dels seus pares, que comprenia la vila de Palau amb la seva església i la capellania d’Argelers. Encara el 1172 Girard II, comte de Rosselló, feu donació d’aquest lloc i de la seva església a l’orde del Temple. L’església ocupa una sala de l’antic castell (segles XIV-XV). Era coberta d’un fustam aparent sobre arcs de diafragmes i havia conservat elements de la seva decoració pintada del segle XIV. Malauradament una “restauració” recent, totalment aberrant, ha fet desaparèixer el fustam medieval, juntament amb el retaule de l’altar major del 1648, obra de l’escultor Llàtzer Tremulles el Vell. L’església posseeix encara dos retaules del segle XV, un calze daurat també del XV i una curiosa estatueta de la Mare de Déu que s’obre i conté una estatueta de Jesús al seu interior, datable al segle XVI.
Al segle XVII l’església parroquial de Palau fou consagrada a sant Sebastià, advocació que manté avui dia.