Il museo, come istituzione, venne fondato nel 1882 durante l'occupazione britannica di Cipro, a seguito di una petizione popolare, la quale venne consegnata all'amministrazione britannica da una delegazione guidata dai leader religiosi sia cristiani che musulmani dell'isola: le principali motivazioni che portano a questa proposta fu il gran numero di scavi illegali che venivano svolti e il contrabbando di opere di antiche che ne derivava[1]. Pochi anni prima dell'istituzione del museo, infatti, Luigi Palma di Cesnola aveva portato fuori da Cipro circa 35 000 reperti, molti dei quali distrutti durante il trasporto, mentre quelli superstiti furono esposti al Metropolitan Museum of Art di New York.

Inizialmente il museo venne finanziato con donazioni privati e ospitato negli uffici governativi; il trasferimento nella sede definitiva avvenne nel 1889. Tuttavia i lavori di costruzione di un nuovo edificio, realizzato al posto del precedente, avvenne nel 1908 ed era originariamente dedicato alla memoria della regina Vittoria: fu progettato dall'architetto Nikolaos Balanos della Società Archeologica di Atene e la costruzione fu supervisionata da George H. Everett Jeffery, allora curatore del museo[2]. Nel 1961 fu aggiunta una seconda serie di gallerie, magazzini e uffici.