Η πρώτη αρχαιολογική συλλογή δημιουργήθηκε στο Ηράκλειο το 1883, με πρωτοβουλία του Φιλεκπαιδευτικού Συλλόγου Ηρακλείου, ο οποίος, με πρόεδρο τον φιλάρχαιο γιατρό Ιωσήφ Χατζηδάκη, κατάφερε να εξασφαλίσει την εξουσιοδότηση της οθωμανικής κυβέρνησης για την ίδρυση της πρώτης «αρχαιολογικής υπηρεσίας›. Η συλλογή στεγάσθηκε σε δύο δωμάτια στην αυλή της μητρόπολης του Αγίου Μηνά και μέχρι το 1900 εμπλουτίσθηκε με δωρεές φιλάρχαιων πολιτών, με εξαγορές αρχαίων αντικειμένων και με τα ευρήματα των πρώτων μικρών ανασκαφών και περισυλλογών. Το 1900, με την έναρξη των μεγάλων ανασκαφών στο νησί, περιέλαβε τα πρώτα σημαντικά ευρήματα, ενώ ταυτόχρονα παραχωρήθηκε στη νεοσύστατη Κρητική Πολιτεία. Τότε μεταστεγάσθηκε σε τμήμα του κτηρίου των Στρατώνων, της σημερινής Νομαρχίας Ηρακλείου, με τη φροντίδα των πρώτων Εφόρων Αρχαιοτήτων, Ιωσήφ Χατζηδάκη και Στεφάνου Ξανθουδίδη.

Το 1904-1907 κατασκευάσθηκε η πρώτη μουσειακή αίθουσα, στη θέση όπου ήταν τα ερείπια της ονομαστής βενετικής μονής του Αγίου Φραγκίσκου, δίπλα στο Χουνκιάρ Τζαμί, ενώ το 1908, μετά την προσθήκη μίας δεύτερης αίθουσας, μεταφέρθηκαν εκεί οι αρχαιότητες. Το 1912, το μικρό αυτό κτίσμα πήρε τη μορφή κλασικιστικού κτηρίου με την προσθήκη της δυτικής πτέρυγας, σε σχέδια του αρχιτέκτονα W. Doerpfeld και του Γραμματέα της Αρχαιολογικής Εταιρείας Αθηνών, Παναγή Καββαδία. Το μουσείο σταδιακά περιέλαβε τα ευρήματα των μεγάλων ανασκαφών που διεξάγονταν σε όλο το νησί από Έλληνες και ξένους ερευνητές.

Η δόμηση του σημερινού κτηρίου, σε σχέδια του αρχιτέκτονα Πάτροκλου Καραντινού, ξεκίνησε το 1937 αλλά η έναρξη του Β΄ Παγκοσμίου Πολέμου έθεσε σε μεγάλο κίνδυνο τις συλλογές και το πολύτιμο περιεχόμενο του μουσείου, το οποίο διασώθηκε χάρη στις προσπάθειες του καθηγητή Ν. Πλάτωνα. Υπό την εποπτεία του ξεκίνησαν στις αρχές της δεκαετίας του 1950 οι εργασίες για την επανέκθεση και παρουσίαση των συλλογών και το 1952 το μουσείο επαναλειτούργησε προβάλλοντας και πάλι τους ανεκτίμητους θησαυρούς του.

Το 2014 ολοκληρώθηκε το πρόσφατο πρόγραμμα ανακαίνισης και το Μουσείο Ηρακλείου, ανανεωμένο και με σύγχρονη αισθητική, άνοιξε ξανά τις πύλες του για το κοινό. Η νέα έκθεση αναπτύσσεται σε 27 αίθουσες, όπου οι συλλογές παρουσιάζονται με σύγχρονη μουσειολογική αντίληψη και υποστηρίζονται με ενημερωτικό και εποπτικό υλικό. Οι δώδεκα αίθουσες του ισογείου είναι αφιερωμένες στο μινωικό πολιτισμό, τον πρώτο αστικό-ανακτορικό πολιτισμό στην Ευρώπη. Η εξωστρέφεια των παραθαλάσσιων κρητικών κέντρων και η κυριαρχία των θαλασσοδρόμων Μινωιτών στο Αιγαίο, που συνδέεται με τους αρχαίους μύθους για τον ημίθεο βασιλιά της Κνωσού Μίνωα, αποτελεί βασικό άξονα της εκθεσιακής αφήγησης. Η περιήγηση συνεχίζεται στην πρώτη αίθουσα του ορόφου με την έκθεση των μινωικών τοιχογραφιών και με τα ευρήματα των ιστορικών χρόνων (10ος αι. π.Χ. έως 3ος αι. μ.Χ.). Η ίδρυση των Κρητικών πόλεων, η λατρεία στα οργανωμένα ιερά, καθώς και ιδεολογικές πεποιθήσεις και πρακτικές που σχετίζονται με τη μεταθανάτια ζωή αναδεικνύονται μέσα από επιγραφές, ταφικά κτερίσματα, πήλινα ειδώλια, ψηφιδωτά. Παράλληλα, οι δύο αίθουσες της συλλογής γλυπτών στο ισόγειο περιλαμβάνουν αρχιτεκτονικά γλυπτά και αγάλματα από τον 7ο αιώνα π.Χ. έως τον 3ο αιώνα μ.Χ.