Il museo è ospitato nel Castello "ex carcere", un torrione inserito nelle mura cittadine, che venne utilizzato come prigione tra il XVII secolo e il 1973. Precedentemente la sede era stata quella del Palazzo Vagliasindi, danneggiato da un bombardamento della seconda guerra mondiale nel 1943.

Il museo raccoglie reperti del VI-IV secolo a.C., provenienti dalla collezione ottocentesca di Paolo Vagliasindi, rinvenuti per la maggior parte nella contrada Sant'Anastasia di Randazzo. Altri oggetti vennero riportati alla luce nella stessa località dagli scavi di Antonino Salinas (1898-1899) e di Paolo Orsi (1904). Tra questi spicca l'"Oinochoe Vagliasindi", una oinochoe attica a figure rosse sulla quale è raffigurato il raro mito delle Arpie che infastidiscono il re cieco Fineo e vengono punite dai Boreadi (Zete e Calaide).