O Paço de Sintra é referido pela primeira vez por Al-Bakrî, geógrafo árabe do século XI, juntamente com o castelo que lhe faz face no alto da serra, hoje denominado Castelo dos Mouros. Nesse documento faz-se uma descrição de Sintra:

«(...) é uma das vilas que dependem de Lisboa no Andaluz, nas proximidades do mar. Está permanentemente mergulhada numa bruma que não se dissipa. O seu clima e os seus habitantes vivem longo tempo. Tem dois castelos que são de extrema solidez (…) A vila está a cerca de uma milha do mar. Há aí um curso de água que se lança no mar e serve para a rega das hortas (…) A região de Sintra é uma das regiões onde as maçãs são mais abundantes. Esses frutos atingem uma tal espessura que alguns chegam a ter quatro palmos de circunferência. Acontece o mesmo com as peras. Na serra de Sintra crescem violetas selvagens.»

Na localização do palácio, no chamado Chão da Oliva, situava-se, provavelmente, a residência dos governadores mouros, cujos vestígios estão por encontrar.