I primi insediamenti umani, almeno secondo ciò che le ricerce archeologiche hanno accertato sino ad ora, ma non è detto che non si scoprano altre prove che arretrino ulteriormente la datazione, sono stati individuati nell'area della città capoluogo, nella grotta di San Teodoro e nella grotta di Sperlinga.

Le fluttuazioni delle popolazioni hanno lasciato tracce risalenti al Paleolitico superiore (da 30.000 a 20.000 anni a.C.) e al Mesolitico (da 20.000 a 6.000 anni a.C.). Nella grotta detta rifugio della Sperlinga, a 5 km da Novara di Sicilia, e nella grotta di San Teodoro, vicino ad Acquedolci, sul versante tirrenico, sono riscontrabili tracce di arte rupestre.
La grotta di San Teodoro si è peraltro rivelata importante deposito lacustre del Quaternario, con resti fossili datati 200.000 anni fa e rappresentanti in prevalenza ippopotami.
A Messina, durante i lavori della ricostruzione postbellica, sono emersi resti di villaggi neolitici ed eneolitici, il che 'racconta' come quegli esseri viventi organizzati in gruppi di cacciatori, attraverso le generazioni abbiano sentito la necessità di un nuovo tipo di stanziamento stabile, operando una scelta funzionale dei siti.
Dalle selci lavorate, alle ceramiche, ai metalli, ogni reperto che testimonia il cammino dell'uomo in riva allo Stretto, sollecita la fantasia dell'uomo moderno.

Le ultime due fasi protostoriche iniziano rispettivamente nel 6.000 a.C. (Neolitico) e nel 4.000 a.C. (Eneolitico), per finire nel II millennio a.C. circa. Intanto la flora e la fauna si sviluppavano arrichendosi e quindi offrendo all'uomo primitivo nuovi pretesti e occasioni per 'inventare' utensili e mezzi sempre più raffinati per vivere e sostentarsi.
I mutamenti del clima durante l'era quaternaria (iniziata 2 milioni di anni fa) aiutarono il nuovo arrivato nella scala biologica umana: l'Homo sapiens, che anche nelle zone messinesi si acclimatò e accelerò la sua evoluzione.
A Messina, inoltre, si sono accertati gli influssi delle culture che si susseguirono nelle Eolie, culture che a loro volta risentirono delle civiltà mediterranee orientali, negli aspetti strumentali ed artistici.
Gente di montagna e gente di mare: questa sembra essere stata nella preistoria la condizione esistenziale di quegli individui sollecitati dalle esigenze di nutrizione con i prodotti della caccia e della vegetazione spontanea che, stante la meridionalità dei siti, potè resistere meglio alle glaciazioni.

Nella Sicilia orientale, secondo le osservazioni degli archeologi, si registrò anche una maggiore permeabilità "ai successivi stimoli di provenienza egea ed anatolica di quanto non lo sarà la parte occidentale"; ma prima di questa evoluzione culturale, altre fasi, tuttora intrise del fascino di leggende e di deduzioni storicistiche per le citazioni e per i raffronti magari poetici, raccontano l'avvicendarsi di popoli nella cuspide orientale dell'isola.

Storia fantastica dunque, ma non tanto: storia che potremmo fare iniziare, il condizionale è d'obbligo, dal IV millennio a.C. Una popolazione stanziale, trasmigrata oltre lo Stretto durante i millenni, si trasformò mediante gli impulsi che provenivano dal Mediterraneo orientale e dalle Eolie. Secondo alcuni, a fondare Messina furono gli zanclei partiti da Candia, guidati dal re Minosse, ma è vicenda antecedente al Paleolitico che ha soltanto il fascino della leggenda.
Quel che è certo, invece, riguarda l'arrivo dei sicani attorno al 1270 a.C.; secondo lo storico greco Tucidide, essi provenivano dalla penisola iberica, messi in fuga dai liguri, e arrivarono nell'isola dove a loro volta sconfissero i mitici ciclopi, lestrigoni e giganti. Ma gli arrivi non cessarono: si ha motivo di ritenere che dal nord siano approdati dopo gli ausoni, abitanti provenienti dalle coste tirreniche sino alla Calabria e componenti una popolazione autoctona della penisola, i profughi focesi e infine i siculi, probabilmente provenienti dalla Liguria, guidati dal leggendario re Siculo.