L'antichità della terra di Milazzo si perde nel mito, tanto che la tradizione ricorda la Grotta di Polifemo ubicata sul costone della Rocca su cui ora sorge il Castello. La leggenda racconta che Polifemo governava gli armenti del Dio Sole, in questa terra (chiamata Chersoneso d’Oro) cantata dai greci per la bellezza, il clima e la fertilità, quando Ulisse, uomo dal multiforme ingegno, vi approdò dopo un naufragio.

Fin qui il mito, testimoniato da ritrovamenti archeologici risalenti al 4000 a.C, ovvero alla civiltà di Tapsos (XIV-XIII a.C.) ed a quella ‘Villanoviana’ (X-XIII a.C.). Molti storici individuano la data della sua fondazione ad opera dei greci nel 716 a. C. Altri sostengono, invece, che furono i Siculi a creare il primo nucleo abitativo.

La storia ricorda memorabili battaglie svolte nel mare che fronteggia l'abitato. Contesa da Ateniesi, Siracusani, Mamertini e Cartaginesi tra i secolo VIII a.C. e il 275 a.C. Ellenizzata dai greci di Messina (allora denominata Zancle), Milazzo fu indipendente dalla città vicina, almeno fino al 550 a. C. Fu assediata dal greco Lachete nel 427 a. C. e nel 270 a. C. fu conquistata dal dittatore siracusano Gerone II, che se ne impossessò dopo la battaglia nei “Campi Milesi contro i Mamertini.

Famosa la battaglia del 260 a.C. che vede il trionfo navale, durante la prima guerra punica, della flotta romana, dotata dei famosi “corvi” (dei ponteggi con uncini), comandata da Caio Duilio contro i cartaginesi di Annibale Barca e quella del 36 a.C. con la quale l’imperatore Ottaviano, vittorioso su Sesto Pompeo, inizia la storia imperiale di Roma (guerra civile romana). Con quest'ultima vittoria Mylae (così è denominata Milazzo dai Romani) diviene Municipio Romano e si fregia dell'Aquila imperiale (che campeggia nel suo stemma municipale) con il detto “Aquila mari imposita– Sexto Pompeo superato”.
Milazzo fu una tra le prime sedi vescovili siciliane durante il periodo bizantino.

Gli Arabi condotti da Fadhl Ibn Giafar, nell’843, l’espugnarono impossessandosene. Durante il periodo musulmano la cittadina divenne un importante centro agricolo e commerciale, che ne fece un grande centro commerciale marittimo per l'esportazione proprio dei prodotti agricoli della sua Piana. Essa aumentò d’importanza essendo a capo di una nuova ripartizione territoriale definita "Tallo di Milazzo".Gli arabi introdussero anche la pesca del tonno, che attecchì fortemente sul luogo e che verrà sempre più sviluppata con l’introduzione di tecniche moderne.
I bizantini tentarono nell’888 di riappropriarsi di Milazzo con una incursione navale a sorpresa. Furono, tuttavia, respinti.
Iniziano anche la fortificazione della Rocca e la costruzione delle mura e del Castello (oggi rimane la cosiddetta torre ‘Saracena’). Da questo momento la storia del Centro si identifica con quella della sua roccaforte. Da Ruggero d'Altavilla in poi la città è il baluardo difensivo di Messina sul Tirreno.
Durante la monarchia di Federico II di Svevia e di Alfonso d'Aragona, il castello fu notevolmente potenziato e inserito fra i "castra exenta" sotto la diretta giurisdizione reale. La Città regia sempre più fortificata acquisisce privilegi nella partecipazione ai più importanti eventi del secolo XIII. L'antico "Vallo" denominato "Comarca di Milazzo" diede alla città un’autorità che perdurò sino al Settecento (era riservata ai magistrati civici, militari e giudiziari).
La sua importanza ne fece punto di scontro tra angioini e aragonesi con il castello come scena dello scontro stesso. Durante la guerra del Vespro del 1282, Milazzo fu a turno presa dai due sovrani combattenti: sia Carlo d'Angiò che Pietro d'Aragona. Divenne sede del Generale Parlamento di Sicilia nel 1295. Nell'inverno di quell’anno, infatti, si tenne l' "Assise del Real Parlamento di Sicilia" nel salone del Maschio del castello milazzese, convocato da Federico II d'Aragona, per discutere il tradimento del fratello Giacomo, in combutta con gli angioini.