La prima notizia dell'esistenza di un castello a Sintra risalgono al geografo arabo Abu ʿUbayd al-Bakri (secolo X). Successivamente si ha notizia che il re Giovanni I ne fece dono al conte di Seia Henrique Manuel de Vilhena nel 1383, anche se dopo pochi anni la costruzione tornò in possesso della casa reale.

Il palazzo venne ricostruito a partire dal 1489, quando prese il via una campagna di lavori finalizzata ad alleggerire la massa muraria dell'edificio e ad arricchirne la decorazione interna, con l'applicazione di azulejos andalusi.

Fra il 1505 e 1520 venne costruita la cosiddetta ala manuelina e nel 1508 iniziò la costruzione della sala degli scudi (Sala dos Brasões).

Nel 1755 vennero effettuati importanti lavori di restauro a seguito dei danni causati dal terremoto di Lisbona, nel corso dei quali venne edificata l'ala che va dal Jardim da Preta al Pátio dos Tanquinhos.

Negli ultimi anni della monarchia il palazzo divenne la residenza estiva della regina madre, Maria Pia di Savoia, ultima reale a vivere a Sintra. Nel palazzo si tennero diversi ricevimenti organizzati dalla regina madre per accogliere gli statisti che si recavano in visita in Portogallo, tra cui l'imperatore Guglielmo II e il presidente della Francia, Emile Loubet.

Nel 1910 il palazzo venne dichiarato monumento nazionale.