Η παρουσία του ανθρώπου στα Μάλια κατά τη Νεολιθική εποχή (6000-3000 π.Χ.) αποδεικνύεται μόνο από κομμάτια πήλινων αγγείων. Η κατοίκηση στην περιοχή υπήρξε συνεχής από τα μέσα της 3ης χιλιετίας ως το τέλος της προϊστορίας. Έχουν αναγνωριστεί κατοικίες προανακτορικού οικισμού (2500-2000 π.Χ) κάτω από το ανάκτορο και ταφές της ίδιας εποχής κοντά στη θάλασσα.

Γύρω στα 2000-1900 π.Χ. υπολογίζεται πως έχει κτιστεί το πρώτο ανάκτορο της πόλης. Ο ήδη ανεπτυγμένος οικισμός, συνοικίες του οποίου σώζονται γύρω από το ανάκτορο, μετατρέπεται σε ανακτορικό κέντρο-πόλη. Το πρώτο αυτό ανάκτορο καταστρέφεται γύρω στα 1700 π.Χ από σεισμό. Νέο ανάκτορο ανοικοδομείται γύρω στα 1650 π.Χ., στην ίδια θέση διατηρώντας το βασικό σχεδιασμό του προηγούμενου, ενώ λιγοστές αλλαγές έγιναν 50 χρόνια αργότερα.

Η καταστροφή του νέου ανακτόρου σημειώνεται παράλληλα με την καταστροφή των άλλων γνωστών μινωικών κέντρων, στα 1450 π.Χ. περίπου. Μικρή περίοδος ανακατάληψης υπήρξε τον 14ο-13ο αιώνα π.Χ. Στην περιοχή "Μάρμαρα" υπάρχουν εκτεταμένα ερείπια οικισμού ρωμαϊκών χρόνων και βασιλική του 6ου αιώνα.