Human presence at Malia during the Neolithic period (6000-3000 B.C.) is attested only by potsherds, but habitation was continuous from the middle of the 3rd millennium B.C. until the end of Prehistory. Houses of a Prepalatial settlement (2500-2000 B.C.) have been found under the palace, while graves of the same period are located near the sea. The first palace was built in around 2000-1900 B.C. The already existing significant settlement of which are preserved parts around the palace, was then converted into a palatial centre-city. The palace was destroyed in around 1700 B.C. and rebuilt in 1650 B.C. at the same site, following the plan of the older palace, while a few changes took place 50 years later. The destruction of the new palace came in c. 1450 B.C., along with the destruction of the other Minoan palatial centres. The site was reoccupied for a short period in the 14th-13th century B.C. Remains of a Roman settlement cover an extensive area at the site called "Marmara", where a basilica of the 6th century is also preserved.

The English admiral Th. Spratt, who travelled in Crete in the middle of the 19th century, reports the finding of gold sheets at the site "Helleniko Livadi". In 1915, Joseph Chatzidakis started a trial excavation on the hill called "Azymo", and brought to light the southern half of the west wing of the palace, as well as the tombs by the sea, but he stopped the investigation. Finally, the French School of Archaeology at Athens resumed the excavations, which are continued until today with intervals, at the palace, the sectors of the town and the cemeteries on the coast. The results have been published in the series of "Etudes Cretoises" since 1928, and in the works of H. Van Effenterre and O. Pelon. The finds are exhibited in the Museum of Herakleion, and some in the Museum of Aghios Nikolaos.