O palacio atópase na zona de Holyrood, no extremo da Milla Real, a rúa principal da zona vella da cidade, chamada precisamente así porque une no seu extremo oeste o castelo de Edimburgo co palacio de Holyrood, no extremo leste.
O conxunto foi fundado inicialmente como un mosteiro por David I de Escocia, en 1128. Serviu como principal residencia dos reis e das raíñas da Escocia desde o século XV. Dende a unión das coroas británicas, o palacio é usado polos monarcas británicos como a súa residencia oficial cando están en Escocia. Na actualidade a raíña raíña Sabela II, adoita usar o palacio no inicio de cada verán.
Unha das lendas referidas sobre o palacio conta que unha vez un soldado foi destinado a explorar se había túneis que comunicasen este edificio co castelo, situado a unha milla de distancia e montaña arriba. Como o soldado se perdeu e nunca máis volveu, disque se escoita a canción que cantaba de cando en cando, entre as paredes dos castelo.[Cómpre referencia]
