Το κτίριο που φιλοξενεί το βυζαντινό μουσείο Βεροίας ιδρύθηκε στις αρχές του 20ου αι. Η κατασκευή του άρχισε το 1908 και ολοκληρώθηκε το 1911 από το Στέργιο Μάρκου, γιατρό με σπουδές στο Βουκουρέστι. Σε επαφή με τη νότια όψη του περνούσε νερό από παρακλάδι του Τριπόταμου, το οποίο αποτελούσε την κινητήρια δύναμη για τη λειτουργία του μύλου. Πρόκειται για αλευρόμυλο που λειτουργούσε με κυλίνδρους.

Το κτίριο ήταν τετραώροφο, τυπικό δείγμα της αρχιτεκτονικής βιομηχανικών κτιρίων της περιόδου. Η τοιχοποιία του είναι ιδιαίτερα εντυπωσιακή, καθώς αποτελείται από τοπικό πωρόλιθο και ισχυρό ασβεστοκονίαμα και ενισχύεται στις γωνίες με λαξευμένα αγκωνάρια. Τα πατώματα και η στέγη ήταν ξύλινα και εδράζονταν στις περιμετρικές τοιχοποιίες και σε μεταλλικό σκελετό από χυτοσίδηρο. Το κτίριο λειτουργούσε έως τη δεκαετία του 1960 ως αλευρόμυλος ενώ το 1981 κάηκε και ό,τι απέμεινε ήταν οι περιμετρικές τοιχοποιίες και ο μεταλλικός σκελετός εξαιρετικά παραμορφωμένος.

Το Υπουργείο Πολιτισμού αναγνωρίζοντας την αξία του κτιρίου ως ιστορικού διατηρητέου μνημείου της πόλης προχώρησε στην απαλλοτρίωσή του και στη συνέχεια στην αποκατάστασή του και τη μετατροπή του σε βυζαντινό μουσείο.

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

Σήμερα είναι προσιτή στον επισκέπτη η πρώτη από τις μόνιμες εκθέσεις που οργανώθηκε από τη Διεύθυνση Βυζαντινών και Μεταβυζαντινών Μνημείων του ΥΠ.ΠΟ. σε συνεργασία με την Εφορεία μας και εγκαινιάσθηκε από τον τέως Πρωθυπουργό κ. Κων/νο Σημίτη και έχει ως θέμα την επικοινωνία στο βυζαντινό κόσμο, η προσωρινή έκθεση για την αποκατάσταση του κτιρίου και τη μετατροπή του σε μουσείο, το περίπτερο ηλεκτρονικής πληροφόρησης για τα μνημεία της πόλης και τα ταξίδια των ζωγράφων και το εκπαιδευτικό πρόγραμμα που παρακολουθεί την οργάνωση της μόνιμης έκθεσης.

Το μουσειολογικό πρόγραμμα θα ολοκληρωθεί έως το έτος 2006 με την παρουσίαση του αστικού και ιδιωτικού βίου της Βεροίας στο δεύτερο όροφο και της λατρείας, ως χώρου όπου τελείται η λατρευτική πρακτική, αλλά και ως σχέση επικοινωνίας του ανθρώπου με το θείον μέσα από την αντίληψη για το λατρευόμενο πρόσωπο και την αγιότητα στον τρίτο όροφο. Παράλληλα προβλέπεται η επέκταση του μουσείου προς βόρεια με την αποκατάσταση τριών παλαιών κατοικιών ιδιοκτησίας του ΥΠ.ΠΟ. επί του τείχους της πόλης και τη μετετροπή τους σε μικρή βιβλιοθήκη-αναγνωστήριο, αναψυκτήριο, χώρους διοίκησης και μικρές αποθήκες.