Το κτήριο στο οποίο στεγάζεται το Μουσείο, κτίσθηκε ως κατοικία της οικογένειας του τραπεζίτη Γιακό Μοδιάνο σε σχέδια του αρχιτέκτονα Ελί Μοδιάνο. Αποτελεί αξιόλογο δείγμα εκλεκτικισμού με εμφανείς τις επιδράσεις της γαλλικής σχολής και εντυπωσιακό στοιχείο το διώροφο σκεπαστό εξώστη της δυτικής γωνίας του κτηρίου (λότζα) που έχει θέα προς τη θάλασσα. Το 1913 αγοράστηκε από το ελληνικό δημόσιο, παραχωρήθηκε στη βασιλική οικογένεια και χρησιμοποιήθηκε ως κατοικία του εκάστοτε γενικού διοικητή της Μακεδονίας. Στο κτήριο στεγάστηκε αργότερα η Στρατιωτική Ιατρική Σχολή καθώς και η Ιερατική Σχολή.

Το 1970, με την παραχώρηση της χρήσης του κτηρίου στο Λ.Ε.Μ.Μ.Θ, αρχίζουν οι εργασίες επισκευής, συντήρησης και διαμόρφωσης των εκθεσιακών χώρων σύμφωνα με μελέτη του καθηγητή του Α.Π.Θ. Ν.Μουτσόπουλου.

Το κτίσμα και η αυλή του κηρύχθηκαν διατηρητέα μνημεία το 1980.

Μετά από μικρής έκτασης επισκευές και επεμβάσεις, το 1995 ξεκίνησε από την 4η Εφορεία Νεωτέρων Μνημείων η αποκατάσταση του κτηρίου, με σκοπό την προσαρμογή του στις απαιτήσεις ενός σύγχρονου μουσείου. Το έργο χρηματοδοτήθηκε από την Ευρωπαϊκή Ενωση, τον Οργανισμό Θεσσαλονίκη Πολιτιστική Πρωτεύουσα 1997 και το Υπουργείο Πολιτισμού.