La politica pontificia affidò l'impresa dell’offensiva contro gli Arabi ai Normanni che, capeggiati da Tancredi D'Altavilla, erano, tra i gruppi dei soldati di ventura, i più temibili per brama di preda, per audacia e per spietatezza. Nel 1078 Ruggero, il figlio più giovane di Tancredi, espugnò Almoezia e la città riprese il nome di Tauromenium.
Nel 1087 i Normanni occuparono l'intera isola e si trovarono innanzi al problema di sanare le tremende ferite della guerra. In questo compito furono eccellenti, dimostrando di essere una delle dinastie più illuminate del tempo. Si avviò indubbiamente con essi una nuova era di prosperità per la Sicilia.
Avendo spirito di tolleranza, non scacciarono gli arabi dall'isola; allontanarono soltanto i capi, relegandoli nei castelli della Calabria, della Puglia e dell'Irpinia. Assegnarono delle terre con il privilegio dell'immunità perpetua agli ordini monastici di obbedienza greca e ai vescovadi cattolici. Fecero riaprire gli edifici destinati al culto cristiano, consentendo che le campane fossero di nuovo issate sulle chiese. Venne affermato il dominio del sovrano sulle acque e sui boschi e riconosciuto agli abitanti il diritto di pascolo, ghiandaggio e legnatico sulle terre demaniali e comunali. Ripresero, infine, gli scambi commerciali, pur persistendo ancora il baratto.
La lingua ufficiale preesistente - un misto di greco e arabo - si trasformò e la parlata comune si arricchì di nuove acquisizioni lessicali, sintattiche e fonetiche. Nacque così la cosiddetta lingua volgare.
La dinastia normanna si esaurì negli ultimi decenni del secolo XII.
Dopo i Normanni, la Sicilia fu dominata dagli Svevi. Federico II (l194-1250) fu uno dei protagonisti più illuminati della storia della sua epoca. Durante il suo regno, Taormina godette di un periodo di prosperità mai avuta in altri tempi.
Il dominio svevo, tuttavia, non durò per molto tempo, anche per la netta ostilità del papato.