L'édifice abritant le musée est remarquable par sa propre histoire. À l'origine, il s'agissait de la Grande Mosquée, construite entre 1454 et 1494 sous la gouvernance du vizir Mahmoud Pacha. Cette mosquée, entourée d'autres structures comme des fontaines et une école, témoigne de la période ottomane en Bulgarie. La transformation du lieu en musée archéologique est en soi une aventure historique : il fut d'abord une bibliothèque dès 1880, avant d'être alloué à l'archéologie.