Fil-post fejn illum insibu l-Palazz Verdala kien hemm dwejra mibnija bejn l-1557 u l-1568 mill-Gran Mastru Jean de la Valette-Parisot għal meta kien imur għall-kaċċa. Il-Palazz li nsibu llum inbena mill-Gran Mastru Hughues Loubenx de Verdalle Verdalle fl-1586. Intgħażlu l-inħawi tal-‘Boschetto’ minħabba l-veġetazzjoni folta tal-post, ideali fejn l-annimali selvaġġi li ntelqu hemm mill-Ordni setgħu jimirħu. Il-miġra fil-wied ta’ taħt kienet għejun ta’ ilma kontinwu għal kważi s-sena kollha, b’hekk dil-miġra kienet tisqi u tgħin biex joktru l-flora u l-fawna. L-arkitett Gerolamo Cassar, l-arkitett Malti tal-Ordni, matul it-tmexxija tal-Gran Mastru Verdalle (1582-1595) fassal il-pjanti għal struttura fortifikata biex isservi bħala difiża bażika kontra l-attakki għall-għarrieda mit-Torok li kienu ikollna minn żmien għal żmien. L-aktar fattur prominenti fost l-elementi ta’ difiża li ddaħħlu fid-disinn kien il-foss li jdawwar il-Palazz. Il-ġebel żmarrat minn dal-foss intuża fil-bini tal-Palazz.
Il-Gran Mastri Jean de Lascaris-Castellar (1636-1657) u aktar ’il quddiem il-Gran Mastru Manoel de Vilhena (1722-1736) ikkontribwixxa għat-tisbiħ ta’ dal-Palazz. Wara li l-Ordni tkeċċa minn Malta, il-Palazz Verdala ntuża bħala ħabs militari għas-suldati ta’ Napuljun li kienu ċedew għat-truppi Maltin u Ingliżi. Għal xi żmien wara l-bini serva wkoll bħala fabbrika tal-ħarir u wara tħalla fi stat ta’ abbandun u spiċċa żdingat. Il-Gvernatur Sir Frederick Ponsonby (1827-1836) kien l-ewwel wieħed li pprova jagħmel xi tiswijiet fil-bini, iżda kien fi żmien il-Gvernatur Sir William Reid (1851-1858) li l-bini ġie restawrat għall-ġmiel li kien igawdi qabel.
Il-Palazz Verdala wara serva bħala r-residenza tal-Gvernaturi li komplew jarmawh u jsebbħuh. Fl-1939, mal-bidu tat-Tieni Gwerra Dinjija, dal-Palazz serva bħala post fejn tqiegħdu x-xogħlijiet tal-arti tal-Mużew Nazzjonali.
