Το ισόγειο του χώρου, όπου στεγάζεται το Μουσείο, αποτελούσε τη δυτική απόληξη του Κάστρου του Αγ. Νικολάου στη περίοδο της Ιπποτοκρατίας, όπως δηλώνει το σχήμα και η δομή του, καθώς και οι κανιονιοθυρίδες στη δυτική και βόρεια πλευρά.

Ο όροφος με τις τέσσερις αίθουσες προστέθηκε στα τέλη του 19ου αι. και ήταν η έδρα του Τούρκου διοικητή, τότε που πήρε την ονομασία "Κονάκι".

Το 1975 άρχισε η επισκευή του κτίσματος από την Αρχαιολογική Υπηρεσία και το 1984 λειτούργησε ως Αρχαιολογικό Μουσείο.