Το αρχαιολογικό Μουσείο της Βέροιας άρχισε να κτίζεται στις αρχές της δεκαετίας του 1960 και το 1965 λειτούργησε ως οργανωμένο Μουσείο. Μέχρι τότε, τα αρχαιολογικά ευρήματα της ευρύτερης περιοχής, αλλά και του Νομού, στεγάζονταν σε χώρο του Δημαρχείου, καθώς και σε άλλα δημόσια κτίρια της πόλης.

Με την πρώτη έκθεση του Μουσείου παρουσιάστηκαν στο κοινό ευρήματα από τον πρώιμο νεολιθικό οικισμό της Νέας Νικομήδειας (Α' Αίθουσα) και αντικείμενα των ελληνιστικών και ρωμαϊκών χρόνων (Αίθουσα Β' και Γ'). Μία αίθουσα τέλος είχε παραχωρηθεί ως αποθήκη - εργαστήριο στην 11η Εφορεία Βυζαντινών Αρχαιοτήτων.

Στις αρχές της δεκαετίας του 1990, με την ευκαιρία διοργάνωσης Συνεδρίου στη Βέροια για τη Μακεδονία, απομακρύνθηκαν τα προϊστορικά εκθέματα από την Α' Αίθουσα προσωρινά και τοποθετήθηκαν σημαντικά ευρήματα από ελληνιστικούς τάφους της Βέροιας. Η προσωρινή εκείνη έκθεση των ευρημάτων παραμένει μέχρι σήμερα.

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