I giorni della battaglia furono narrati, in epoca latina, dagli storici Appiano di Alessandria e Svetonio.
I due contendenti si fronteggiavano da più giorni sulla costa siciliana di nord-est. Per la precisione, le truppe di Agrippa erano posizionate nella zona di Tindari (presso Patti), mentre quelle di Pompeo erano arroccate a Mylae (Milazzo). I soldati di Pompeo controllavano anche la costa che da Milazzo portava al Peloro (Messina), comprendente pure Nauloco.
L’avvistamento di alcune navi, consigliò a Pompe di coprirsi maggiormente. I soldati lasciarono all’avversario la zona di Milazzo, arretrando verso Messana. Le milizie di Agrippa occuparono prontamente la nuova posizione. Tuttavia, passavano i giorni e ambedue le parti non giungevano ad uno scontro militate. Prendendo l’iniziativa, Pompeo suggerì alla parte avversa un definitivo scontro navale, dove egli si riteneva più forte. Ottaviano, evidentemente, accettò.

Il 3 settembre del 36 a.C., nel tratto di mare, che andava da Milazzo a Nauloco, avvenne la battaglia navale. Le 300 navi di Pompeo, ancorate a Nauloco, uscirono a scontrarsi con le 300 navi avversarie. Le forze navali erano praticamente uguali per numero. Tuttavia, quelle di Agrippa, oltre ad essere più grosse e armate di artiglieria (come i nemici), a differenza di quelle di Pompeo, erano dotate di un nuovissimo tipo di “rostro” più efficace, insomma, di una nuova tecnologia militare.

La battaglia fu lunga e sanguinosa. Il vantaggio tecnologico permise ad Agrippa di affondare le maneggevoli e veloci navi di Pompeo. Alla fine della giornata, mentre l’ammiraglio Agrippa contava solo 3 navi perse, quelle della fazione opposta furono: 28 navi affondate, e molte altre bruciate o catturate. Solo 17 navi di Pompeo riuscirono a rifugiarsi nel porto della vicina Messina. Praticamente, una vera e propria disfatta totale.
Nel momento della battaglia, narra Svetonio, Ottaviano, in posizione supina, non trovò il coraggio di assistere allo scontro. Rimase “sdraiato sul dorso con gli occhi rivolti al cielo, terrorizzato, rimanendo in quella posizione, senza presentarsi ai soldati, fino a quando Agrippa non mise in fuga la flotta nemica.” (Svetonio, in Augustus).
Dopo la tremenda sconfitta, Sesto Pompeo cercò rifugio in Oriente, ma venne ucciso da sicari, appena un anno dopo. Ottaviano, libero così di agire, attraverso l’estromissione di Marco Emilio Lepido e puntando sulla prossima sconfitta di Antonio raggiunse l’obiettivo di controllare Roma. Ne divenne il primo imperatore, con il nome di Augusto.