This particular area of Vermio, where Naoussa is found today and where Herodotus places the famous "Gardens of Midas", was inhabited from most ancient times by the Vriges, who migrated to Europe before the Trojan War. According to Thucydides and Strabo, these Vriges were persecuted by Caranus, founder of the Macedonian State, while subsequently other Macedonian tribes came and intermixed with the Vrigo - Pelasgian tribes which were left and thus comprised the population of historical times.
Extended ruins in the area between today's Naoussa and the neighbouring villages of the plain reinforce the version that contemporary Naoussa has evolved at the site of a significant city of antiquity, which was found between Veroia and Edessa. The name of this city, according to archaeologists' most recent views, was Mieza. According to local myth, the three children of the mythical king of the area, Veretos, passed their names on as follows: the daughters to the two important cities of Emathia, Veroia and Mieza, while the son, Olganus, metamorphosed into a river god and gave his name to the river known today as the Arapitsa. A bust of Olganus, which was discovered in the Copanos area and dates back to the 2nd century A.D., is now preserved at the Museum of Veroia.
The archaeological site of Mieza - better known by the name of Lefkadia - which today is included for the most part within the limits of the Municipality of Anthemia, had already been located in the 19th century by the French traveler Delacoulonche and the Dane architect K. F. Kinch, but was subject to systematic research only after 1950, with the work of curator of antiquities at that time, Photis Petsas. The existence of settlements from the late Bronze Age, the Iron Age, the Classical, and also the Hellenistic Era has been verified, the Hellenistic being the most significant from the standpoint of surviving monuments (late 4th c. -168 B. C. ). Among the many scattered archaeological findings of the area, the unique great Macedonian tombs (of Judgment, Lyson and Kallikles, Anthemia, Kinch et. al.) and the School of Aristotle in the Nymphaion at Mieza are considered most significant. Rather recently the ancient theatre of the city has come to light and the city's Agora is being excavated.