The pontifical politics entrusted the enterprise against the Arabs to the Normans who, leaded by Tancredi of Altavilla, were the soldiers most dangerous for greed of prey, for audacity and pitilessness. In 1078 Roger, the younger Tancredi's son, stormed Almoezia and the town took back the name of Tauromenium.
In 1087 the Normans occupied the whole island and they had from now on the problem to cure the awful wounds caused by the war. They were excellent in this assignment, demonstrating to be one of the most enlightened dynasties at that time. With them a new age of prosperity began for Sicily. 
They didn't send away the Arabs from the island having a tolerant spirit;
they removed the leaders only, relegating them in the castles of Calabria, Puglia and Irpinia. They assigned the lands with the privilege of perpetual immunity to the monastic orders of Greek obedience and to the Catholic bishoprics.
They reopened the buildings for the Christian cult, allowing that the bells were again hoisted on the churches. The sovereign dominion was imposeded on the waters and on the woods. The right to pasture on the State lands was recognized to the citizen. The commercial exchanges, at last, revived the island, even if the barter was still persisting. 
The pre-existing official language - a mixture of Greek with Arab language- changed and the common language got rich of new lexical acquisitions, syntactic and phonetic. It was then that the so-called vernacular language began to be speaked.
The Norman dynasty ended in the last decades of the twelfth century. 
After the Normans, Sicily was dominated by the Swabians. Frederic the Second (l194-1250) was one of the most enlighteneded protagonist in his time. During his kingdom, Taormina enjoyed a period of prosperity which never in other times. 
The swabian dominion, however, didn't last for a lot of time, also for the hostility of the papacy.