The promontory was inhabited from the Neolithic , and prehistoric settlement on Capo Milazzo is substantial. Greek colonisation followed: Mylai was established in the eighth century BC, generally credited to settlers from Zancle — the city that became Messina — with some accounts attributing it instead to Cuma. It made itself independent of Zancle around 550 BC , fell to the Athenians in 427 BC , and passed among Carthaginians, Syracusans and Mamertines until Hieron II of Syracuse took it.

Two naval battles in these waters shaped the wider Mediterranean. In 260 BC the Roman admiral Gaius Duilius defeated the Carthaginian fleet off Milazzo — Rome's first victory at sea. Later Marcus Agrippa beat the fleet of Sextus Pompeius here, an event the town still carries on its civic arms: aquila a mari imposita, Sexto Pompeio superato . Under Rome the Milazzesi, as part of the city-state of Messina, held Roman citizen rights and were exempt from the tithe.

The Arabs took the town in 843 and built the core of the castle — the keep with its great tower and eight further towers — and made Milazzo a commercial and agricultural centre. Every subsequent power enlarged it: Normans, then Frederick II of Swabia in the thirteenth century, the Aragonese in the fifteenth, the Spanish in the sixteenth. Under James and Frederick II of Aragon the town was a royal seat and the fortress of the viceregal power in Sicily. In 1718 the citadel held out against a Spanish siege. During the Napoleonic wars it served as a base for British operations in the Mediterranean.

Then 1860 . Between 17 and 24 July , Garibaldi's forces — the Thousand reinforced by later landings, principally the Medici expedition, forming the first nucleus of the Southern Army — fought the Bourbon army in and around the town. Roughly ten thousand men were engaged; the decisive day was 20 July , and the castle garrison capitulated on the 25th . Some of the fiercest fighting took place at the Tonnara , the old tuna-fishing works by the port. It was the victory that opened the road to Calabria and Naples, and it cost the town: the Duomo Antico inside the citadel was so badly damaged on 20 July that it was deconsecrated the same year.

Milazzo also produced one of Italy's most decorated naval officers, Luigi Rizzo , twice awarded the gold medal for valour, commemorated in a museum in the town.