The first archaeological collection of the city of Heraklion was constituted in 1883 with the initiative of the local Association of Friends of Education, which was headed by the doctor and antiquarian Joseph Chatzidakis. Chatzidakis also obtained permission from the Ottoman authorities to establish the first 'archaeological service'. The collection was housed inside two rooms in the courtyard of the cathedral of Saint Minas, and by 1900 was enriched with private donations, new acquisitions and finds from the first small excavations and surface surveys. After large-scale excavations began on the island in 1900, the archaeological collection housed the first important finds. Around that time the museum was ceded to the newly established Cretan state and was subsequently moved to the barracks building of the modern nome of Herakleion under the first Keepers of Antiquities Joseph Chatzidakis and Stephanos Xanthoudidis.

The first display room was built in 1904-1907 over the remains of the famous Venetian monastery of Saint Francis, next to the Hounkiar Djami. The antiquities' collection was moved there after the addition of a second room in 1908. In 1912, this small building was given a Neoclassical appearance with the construction of a west wing designed by architect Wilhelm Dorpfeld and Panagis Kavvadias, Secretary of the Athens Archaeological Society. The collection continued to be enriched by the finds from the great excavations by Greek and foreign archaeologists.

The construction of the current museum began in 1937 on plans by architect Patroklos Karantinos. During the Second World War the museum's antiquities were at great risk, but they were saved thanks to the exertions of Professor Nikolaos Platon. Platon supervised the re-exhibition of the museum's treasures and the museum opened its doors to the public in 1952. The display illustrated the chronological development of Minoan civilization, the history of archaeological research and of the great discoveries on Crete during the early twentieth century (Knossos, Phaistos and Malia palaces etc), and the prevalent theories on Aegean Prehistory. In 1962 the museum bought the collection of the Cretan doctor Stylianos Giamalakis, which was displayed on the first floor. In 1964 the new wing was added to the building and the museum's director Stylianos Alexiou subsequently completed the exhibition.

The latest project of renovation of the Heraklion Museum was completed in 2014. The new exhibition philosophy was organized according to modern museological standards and combines a chronological axon with an enriched thematic narration. Two unifying themes, the dominance of the seafaring Minoans in the Aegean Sea and the foundation of the first urban centres on Crete in the 2nd millennium BC, structure the display in the ground floor galleries. The development of the city-state is the main idea for the second floor display, which covers the period from the beginning of the Iron Age through to the Roman period. This museological narrative is supported by continuous glass showcases, whose annotated colorful frames guide the visitor by indicating the comprehensive themes into which the exhibits have been grouped (such as settlements, trade, death, religion, administration, e.t.c.). Along with introductory texts and captions in Greek and English for the general public and expert alike, these displays bring to life both the day-to-day functioning and the long-term nature of ancient socio-economic organization. Digital media applications launched on large video-screens and touch-screens comprise thematically diverse interpretative video-displays and interactive applications with 3D models as well as digital games, which offer and emotive approach to the exhibits. Investing in another parameter of the museum’s vision to become a site for social inclusion and education, a specialized team has designed educative programs on iPads. Strategies for audience development were also enforced, including a series of musical concerts and other recreation events, specialized talks, thematic guided tours by archaeologists, temporary exhibitions, and heritage-based activities that promote connecting the past with the present.