Így nézhetett ki a palota Mátyás király uralkodásának idején
A palota története akkor kezdődött, amikor 1323-ban Károly Róbert a királyi udvart Visegrádra helyezte, ekkor kezdett építkezni a városban. Az épületegyüttes első említése meglehetősen rossz emlékű: a Képes Krónika szerint Zách Felicián itt támadt rá a királyi családra. Károly Róbert idején csak néhány lakóház épült fel és kialakítottak egy lovagi torna rendezésére alkalmas teret, ahol olykor maga a király is nyeregbe szállt.
Az Anjou korban a terület városrész volt több épülettel, amit Zsigmond uralkodása alatt alakítottak palotává. A palota négyzet alaprajzú volt és fal vette körül. A régi kápolna a falon kívül maradt így azt, kolostorépülettel kiegészítve az obszerváns ferenceseknek adományozta a király.
Főbejáratként a kaputorony szolgált, amivel pontosan szemben volt az új egyhajós palotakápolna bejárata. Az elrendezés módosításával több udvar és kert jött létre. Ezek közül a legjelentősebb a fogadóudvar és az ÉK-i palotán belül kialakított díszudvar volt. Az épületegyüttes ÉK-i részén volt a palota központja. Itt, egy háromemeletes négyzet alaprajzú épületben alakították ki a királyi és királynéi lakosztályokat. Az alsó szinten lakott a személyzet, a felső két szinten pedig a király és a királynő nyári és téli szállása volt. E mellé a palotarész Zsigmond téglalap alakú, a palotával majdnem megegyező nagyságú gyümölcsöskertet alakíttatott ki, aminek közepén vízvezetékkel táplált csorgókút volt.
A
paloták termeiben is megtalálhatók a Zsigmond kori, kényelmi átalakítások és díszítések nyomai. A palotát később némileg elhanyagolták, és ebben csak Hunyadi Mátyás aragóniai Beatrixszal kötött 1476-os házassága hozott változást. A késő gótikus stílusban átépített palotában Itália után Európában először megjelent a reneszánsz építő- és szobrászművészet is.
Kevés új épületet építettek, a régieket alakították át a kor igényei szerint. A szobrok, szökőkutak Giovanni Dalmata a szobrászműhelyében készültek.
Feltehetően az ő nevéhez köthető a palota leghíresebb dísze, a Herkules-kút elkészítése is, amely a magyarországi reneszánsz egyedülálló emléke. Mintaképei az olasz quattrocento szökőkútjai voltak, a kúttál ornamentikája és a gyümölcsfüzérek Andrea Bregno római mester műveivel rokoníthatóak. A kút nyolcszögű medencéjének kávalapjain szalagokkal átkötött gyümölcsfüzérek között Mátyás címerei jelennek meg. A puttók által tartott, drágakőmotívumokkal ékesített kerek kúttál fölé magasodott a kútszobor: Herkules és a lernai hydra küzdelme. A kút vízsugarai az állat torkaiból szökkentek ki. A Mátyás korabeli művészetben Herkules alakja a hadvezér királyt jelképezi, de a gyermek Herkules ábrázolása valószínűleg a hadvezér király törvénytelen fiára, Corvin Jánosra utal.
A Herkules-kút körül a Zsigmond-kori díszudvart átépítve, annak első szintjén reneszánsz loggiát alakítottak ki. A kertben új teraszokat képeztek ki.A kápolnában is megtalálható volt az itáliai reneszánsz stílusában alkotó szobrászok kéznyoma. Aranyozott carrarai márványból alkották meg a kápolna új tabernákulumát, és számos faragvánnyal díszítették a templomot, ami közül egy vörösmárvány dombormű, az un. Visegrádi Madonna ma is megcsodálható.
A palota a korabeli itáliai reneszánsz udvarok között is megállta a helyét, ezért olvasható a sokat látott pápai követ, Bartolomeo de Maraschi leveleiben, hogy a földi paradicsomból ír. Később a 16. század közepén Oláh Miklós Hungária című művében emlékezik meg az épületről.
A palotát a török-kor idején elhanyagolták, és a 18. századra szinte teljesen a föld alá került. A 20. századra elfeledték, és még abban is kételkedtek, hogy valóban létezett az Oláh által megírt formában. A palota helyét végül Schulek János találta meg, és kezdett el ott ásni 1934 végén. Ahogy a palota építéséhez majdnem minden Visegrádon építtető király hozzájárult, úgy a felújításon a Visegráddal foglalkozó leghíresebb régészek, történészek mindegyike dolgozott - Schulek Jánostól Héjj Miklóson át Szőke Mátyásig.
A sokszor évtizedekig akadozó rekonstrukció a millennium közeledtével kapott új lendületet, és 2000-re elkészült az ÉK-palota és a Herkules-kút rekonstrukciója. A palotán belül a kiállítótermek és a kőtár a különböző korokból származó emlékeket mutatja be.