After 250 years of Arab control, Sicily was inhabited by a mix of Christians, Arab Muslims, and Muslim converts at the time of its conquest by the Normans. Arab Sicily had a thriving trade network with the Mediterranean world, and was known in the Arab world as a luxurious & decadent place. It had originally been under the rule of the Aghlabids and then the Fatimids, but in 948 the Kalbids wrested control of the island and held it until 1053. During the 1010s and 1020s, a series of succession crises paved the way for interference by the Zirids of Ifriqiya. Sicily was racked by turmoil as petty fiefdoms battled each other for supremacy. Into this, the Normans under Robert Guiscard and his younger brother Roger Bosso came intending to conquer; the pope had conferred on Robert the title of "Duke of Sicily", encouraging him to seize Sicily from the Saracens.
Robert and Roger first invaded Sicily in May 1061, crossing from Reggio di Calabria and besieging Messina for control of the strategically vital Strait of Messina. Roger crossed the strait first, landing unseen overnight and surprising the Saracen army in the morning. When Robert's troops landed later that day, they found themselves unopposed and Messina abandoned. Robert immediately fortified the city and allied himself with the emir, Ibn at-Timnah, against his rival Ibn al-Hawas. Robert, Roger, and at-Timnah then marched into the centre of the island by way of Rometta, which had remained loyal to at-Timnah. They passed through Frazzanò and the Pianura di Maniace (Plain of Maniakes), encountering resistance to their assault of Centuripe. Paternò fell quickly, and Robert brought his army to Castrogiovanni (modern Enna, the strongest fortress in central Sicily). Although the garrison was defeated the citadel did not fall, and with winter approaching Robert returned to Apulia. Before leaving, he built a fortress at San Marco d'Alunzio (the first Norman castle in Sicily).
Roger I receiving the keys of Palermo in 1071
Robert returned in 1064, bypassing Castrogiovanni on his way to Palermo; however, when his camp was infested by tarantulas the campaign was called off. He invaded Palermo again in 1071, but only the city fell; its citadel did not fall until January 1072. Robert invested Roger as Count of Sicily under the suzerainty of the Duke of Apulia. In a partition of the island with his brother Robert retained Palermo, half of Messina, and the largely Christian Val Demone (leaving the rest, including what was not yet conquered, to Roger).
In 1077 Roger besieged Trapani, one of the two remaining Saracen strongholds in the west of the island. His son, Jordan, led a sortie which surprised guards of the garrison's livestock. With its food supply cut off, the city soon surrendered. In 1079 Taormina was besieged, and in 1081 Jordan, Robert de Sourval and Elias Cartomi conquered Catania (a holding of the emir of Syracuse) in another surprise attack.
Roger left Sicily in the summer of 1083 to assist his brother on the mainland; Jordan (whom he had left in charge) revolted, forcing him to return to Sicily and subjugate his son. In 1085, he was finally able to undertake a systematic campaign. On 22 May Roger approached Syracuse by sea, while Jordan led a small cavalry detachment 15 miles (24 km) north of the city. On 25 May, the navies of the count and the emir engaged in the harbour—where the latter was killed—while Jordan's forces besieged the city. The siege lasted throughout the summer, but when the city capitulated in March 1086 only Noto was still under Saracen dominion. In February 1091 Noto yielded as well, and the conquest of Sicily was complete.
The Palazzo dei Normanni was a 9th-century Arab palace in Sicily, converted by the Normans into their governing castle. In 1091, Roger landed at Malta and subdued the walled city of Mdina. He imposed taxes on the islands, but allowed the Arab governors to continue their rule. In 1127 Roger II abolished the Muslim government, replacing it with Norman officials. Under Norman rule, the Arabic spoken by the Greek Christian islanders for centuries of Muslim domination became Maltese.
Read More http://www.wondersofsicily.com/sicily-normans.htm