Seuls des tessons de vases de terre cuite témoignent d’une présence humaine à Malia à l’époque néolithique (6000-3000 av. J.-C.). La région fut constamment habitée du milieu du troisième millénaire à la fin de la Préhistoire.

Des maisons d’une colonie pré-palatiale (2500-2000 av. J.-C.) ont été localisées au-dessus du palais et des tombes de la même époque près de la mer. Le premier palais a été construit vers 2000-1900 av. J.-C. La localité déjà puissante, dont des quartiers sont conservés autour du palais, est transformée en une cité-centre palatial. Le palais est détruit vers 1700 av. J.-C. et reconstruit en 1650 av. J.-C. au même emplacement, sur les plans de l’ancien palais, tandis que quelques changements sont apportés cinquante ans plus tard. La destruction du nouveau palais est survenue à la même époque que celle des autres centres minoens, vers 1450 av. J.-C. Le site fut brièvement réoccupé au XIV^e-XIII^e siècles av. J.-C. Dans la région de Marmara, il existe de nombreuses ruines d’une localité de l’époque romaine et une basilique du VI^e siècle.

L’amiral anglais Th. Spratt qui voyagea en Crète au milieu du XIX^e siècle déclara avoir découvert des feuilles d’or au lieu-dit « Elliniko Livadi ». Joseph Chatzidakis entama des premières fouilles en 1915, sur la colline Azymo, mettant au jour la moitié sud de l’aile ouest du palais et des tombes sur la plage ; il dut cependant cesser les travaux. Finalement, l’École française d’archéologie prit en charge les fouilles qui, malgré des interruptions, se poursuivent jusqu’à aujourd’hui dans le palais, les quartiers de la ville et les nécropoles de la plage. Les publications et études concernant les fouilles figurent dans la série Études Crétoises de 1928, tandis que Η. Van Effenterre et O. Pelon ont procédé à des publications plus complètes. Les pièces découvertes sont exposées au musée d’Héraklion ; certaines se trouvent au musée d’Agios Nikolaos.