Il Museo occupa attualmente l'edificio che fu la Casa dei Padri della Congregazione di S. Filippo Neri e fa parte dell'antico complesso monumentale dell'Olivella che comprende anche la chiesa di S. Ignazio e l'Oratorio di S. Filippo Neri (eretto nel 1769 ad opera di G. Venanzio Marvuglia). Il complesso architettonico, iniziato sul finire del XVI secolo su progetto di Antonio Muttone, fu completato nel XVII secolo.
A seguito della legge sulla soppressione degli ordini religiosi (1866), che prescriveva la confisca dei loro beni, l'edificio divenne sede del Museo Nazionale.Il progetto, denominato Fabbricato dell'Olivella da adattarsi ad uso Museo Nazionale in Palermo, permise di realizzare la sede museale all'interno del convento, implicando trasformazioni irreversibili dell'edificio religioso, dettate dalle esigenze museografiche.
I bombardamenti della seconda guerra mondiale comportarono la distruzione di un'intera ala dell'edificio, in seguito ricostruita su progetto di G. De Angelis D'Ossat. Nel periodo post-bellico, dopo il trasferimento definitivo della sezione medievale e moderna al Palazzo Abatellis e l'istituzione della Galleria Nazionale, si iniziò il nuovo riordinamento del Museo, divenuto esclusivamente archeologico.L'edificio, austero per concezione architettonica e con una struttura volumetrica autorevole, è sviluppato longitudinalmente: lungo un asse, orientato in direzione est-ovest, si susseguono due ampi cortili porticati e una chiostra, sul fondo. Il primo cortile porticato, quello dell'ingresso, è più piccolo dell'altro e possiede elementi architettonici più interessanti. In esso le colonne, non molto slanciate, sorreggono degli archi ribassati che si ispirano a modelli tardo-quattrocenteschi. Le decorazioni architettoniche sono piuttosto marcate, secondo il gusto manieristico che trionfò a Palermo fra Cinquecento e Seicento. Nel secondo cortile, realizzato successivamente, gli archi poggiano su slanciate colonne di stile tuscanico.Il ribaltamento dell'ingresso per motivi di rappresentanza, dalla piazza dell'Olivella alla nuova via Roma con il conseguente rovesciamento dell'Itinerario Museale, fu tra le più sostanziali modifiche apportate all'edificio. Questo comportò la costruzione all'interno del cortile del loggiato, di un corridoio coperto per il collegamento assiale con gli altri cortili, dove, per adattarle al nuovo percorso, vennero perfino ruotate le statue delle fontane.
Il museo è un importante archivio storico in quanto documenta le diverse fasi dell'arte e della civiltà della Sicilia occidentale, dalla preistoria alla tarda età romana e documenta la storia del collezionismo sette-ottocentesco attraverso l'esposizione di importanti collezioni e reperti, in alcuni casi di provenienza non siciliana.