Il terreno è antico — insediamento dell'età del bronzo a Grotte Alte e la colonia greca siracusana di Kamarina sulla costa vicina — ma la città non lo è.

Vittoria Colonna Henriquez-Cabrera si trovò in difficoltà in seguito alla morte del marito, Luigi Enríquez de Cabrera , Ammiraglio di Castiglia, duca di Medina de Rioseco e Conte di Modica. Per risanare il suo patrimonio, chiese a Filippo III di Spagna una concessione per fondare un nuovo insediamento. Il sito scelto fu Boscopiano — il bosco pianeggiante — sulla riva destra della valle dell'Ippari, nella pianura tra l'Ippari e il Dirillo, vicino ai resti di Kamarina. Il diploma reale concesso il 24 aprile 1607 lo stabiliva in questi termini: Riedificetur Camarina , che Kamarina sia riedificata.

La nuova città prese il nome della sua fondatrice. I lavori al castello iniziarono il 4 marzo 1607 e, insieme alla nobile residenza, furono costruiti i granai per il grano della Corte, la prima chiesa di San Giovanni Battista e due mulini. Il castello e la chiesa madre furono posti come i due poli prospettici del piano, e le strade furono tracciate a griglia — la forma ordinaria di una fondazione pianificata, e il motivo per cui Vittoria non assomiglia affatto agli intricati paesi collinari circostanti.

La contessa reclutò la sua popolazione dai comuni della contea. Il patrono, San Giovanni Battista , è attribuito ai vizzinesi che formarono il principale gruppo di insediamento. La terra era estremamente fertile e la città vi crebbe rapidamente, attirando persone dai paesi circostanti, da altre parti della Sicilia, dalla Calabria e da Malta.

Il terremoto del 1693 è l'unico punto in cui le fonti sono realmente in disaccordo: alcuni dicono che distrusse in parte la giovane città, altri che Vittoria subì danni relativamente lievi. Ciò che non è in dubbio è che la ricostruzione — favorita dal terreno pianeggiante — proseguì con la griglia, con strade larghe, dritte e simmetriche, e produsse la chiesa madre come ricostruita tra il 1695 e il 1706 , che custodisce la tomba della fondatrice.

Il XVIII e il XIX secolo portarono denaro ed edifici: la chiesa della Madonna delle Grazie , ricostruita nel 1754 con una facciata a torre e altari in marmo policromo del 1771 ; il neoclassico Teatro Comunale accanto ad essa, costruito tra il 1869 e il 1877 , con il fronte coronato dalle statue di Apollo e Diana; e un consistente corpo di architettura Liberty , con l'influenza dell'architetto palermitano Ernesto Basile.

Un episodio del XX secolo merita di essere menzionato. Nel 1916 Vittoria ospitò un campo di prigionia che conteneva circa ventimila soldati dell'esercito austro-ungarico.