Η πρώτη απόφαση για την ίδρυση Βυζαντινού Μουσείου στη Θεσσαλονίκη περιέχεται σε διάταγμα που εκδόθηκε το 1913, ένα χρόνο, δηλαδή, μετά την απελευθέρωση της πόλης από τους Τούρκους. Ωστόσο, μόλις το 1977 προκηρύχθηκε ο πανελλήνιος αρχιτεκτονικός διαγωνισμός για το κτήριο που θα στέγαζε το μουσείο. Τότε βραβεύθηκε η μελέτη του αρχιτέκτονα Κυριάκου Κρόκου, στον οποίο και ανατέθηκε η σύνταξη των οριστικών μελετών.

Το οικόπεδο για την ανέγερση του μουσείου, που αποτελούσε τμήμα του πρώην στρατοπέδου Τσιρογιάννη, παραχωρήθηκε από το Υπουργείο Εθνικής ’μυνας στο Υπουργείο Πολιτισμού, το 1984. Το έργο της ανέγερσης του μουσείου εντάχθηκε το 1988 στα Μεσογειακά Ολοκληρωμένα Προγράμματα της Ευρωπαϊκής Ένωσης και το κτήριο θεμελιώθηκε το 1989. Η οικοδόμηση του ολοκληρώθηκε το 1993 και την ίδια χρονιά εγκρίθηκαν από το Κεντρικό Αρχαιολογικό Συμβούλιο η τελική ονομασία και η μουσειολογική μελέτη του νέου μουσείου, το οποίο εγκαινιάσθηκε το Σεπτέμβριο του 1994.

Τον πυρήνα των συλλογών του αποτέλεσαν οι αρχαιότητες που είχαν μεταφερθεί το 1916 στο Βυζαντινό και Χριστιανικό Μουσείο της Αθήνας. Το μεγαλύτερο μέρος τους επέστρεψε στη Θεσσαλονίκη και μία επιλογή από αυτές παρουσιάσθηκε στην πρώτη περιοδική έκθεση με τίτλο ''Βυζαντινοί θησαυροί της Θεσσαλονίκης - Το ταξίδι της επιστροφής'', που οργανώθηκε παράλληλα με τα εγκαίνια του μουσείου, το 1994. Τότε το μουσείο υπαγόταν στην 9η Εφορεία Βυζαντινών Αρχαιοτήτων, ενώ το 1997 συγκροτήθηκε ως αυτοτελής υπηρεσιακή μονάδα του Υπουργείου Πολιτισμού, με δική του διεύθυνση.

Από το 1997 άρχισαν να ανοίγουν σταδιακά στο κοινό και οι αίθουσες με τις μόνιμες εκθέσεις του μουσείου. Τότε εγκαινιάσθηκαν οι δύο πρώτες εκθέσεις, με τίτλο ''Από τα Ηλύσια Πεδία στο Χριστιανικό Παράδεισο'' και ''Ο παλαιοχριστιανικός ναός''. Το 1998 εγκαινιάσθηκε η έκθεση ''Παλαιοχριστιανική πόλη και κατοικία'', το 2000 οι εκθέσεις ''Από την Εικονομαχία στη λάμψη των Μακεδόνων και των Κομνηνών'', ''Οι δυναστείες των βυζαντινών αυτοκρατόρων'' και ''Το βυζαντινό κάστρο'', το 2001 άνοιξαν στο κοινό οι εκθέσεις των δύο ιδιωτικών συλλογών, της Ντόρης Παπαστράτου και του Δημήτριου Οικονομόπουλου, ενώ το 2002 εγκαινιάσθηκε η έκθεση ''Το λυκόφως του Βυζαντίου''. Οι δύο τελευταίες εκθέσεις ''Το Βυζάντιο μετά το Βυζάντιο'' και ''Ανακαλύπτοντας το παρελθόν'' εγκαινιάσθηκαν το 2004.

Οι εκθέσεις ''Το Βυζάντιο μετά το Βυζάντιο'' και ''Ανακαλύπτοντας το παρελθόν'', συγχρηματοδοτήθηκαν από την Ευρωπαϊκή Ένωση (Γ΄ Κοινοτικό Πλαίσιο Στήριξης, Επιχειρησιακό Πρόγραμμα Πολιτισμός, 2000-2006) και από το Ελληνικό Δημόσιο (Υπουργείο Πολιτισμού).