Музей был основан в 1882 году по просьбе местного населения во времена британской оккупации острова. Петицию об этом британской администрации передала специальная делегация во главе с религиозными лидерами христианского и мусульманского населения Кипра.[1] Стимулом для этого действия стали несколько незаконных раскопок на острове, а также вывоз контрабандой многих культурных ценностей. Наиболее активным нелегалом в этой области стал археолог, а по совместительству посол США на Кипре, Луиджи Пальма ди Чеснола, который за годы работы на острове вывез оттуда свыше 35000 предметов, представляющих археологическую ценность. Многие из них были разбиты и утеряны во время транспортировки, а уцелевшие стали частью коллекций музея Метрополитен в Нью-Йорке.[2]

На первых этапах своего существования музей выживал за счёт частных пожертвований и размещался не в специальном здании, а в одном из государственных учреждений. В 1889 году музей переехал в новом помещение на улицу Виктории, где разместился в средневековых стенах города. Строительство нынешнего здания началось в 1908 году, и было посвящено памяти королевы Виктории. Музей был построен по проекту архитектора Г. Баланоса из Археологического общества Афин, а его строительством руководил Джордж Эверетт Джеффри, тогдашний куратор музея.[3] В 1961 году у музея появилось дополнительное здание для складов и галерей.