The first archaeological collection of the town of Herakleion was constituted in 1883 with the initiative of the local Philekpaideutikos Syllogos (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 Agios 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 came to include the first important finds from these. 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 D?rpfeld 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. In 2000 the museum acquired the Nikos Metaxas collection, part of which will soon go on display.
In 1987 the building received new electricity, air conditioning and fire protection installations, and the skylights in the display rooms were replaced with false ceilings and artificial lighting. A new refurbishment based on plans by architect Alexandros Tombazis began in 2002; it will include the re-opening of the original skylights, new electro-mechanical installations (air conditioning, lighting, security, fire protection etc) and a new wing of storerooms to the north of the building. It will also highlight the remains of the Venetian church of Saint Francis on the east side of the atrium.