Malta became part of the newly formed Kingdom of Sicily, which also covered the island of Sicily and the southern half of the Italian Peninsula. The Catholic Church was reinstated as the state religion, with Malta under the See of Palermo, and some Norman architecture sprang up around Malta, especially in its ancient capital Mdina. King Tancred made Malta a fief of the kingdom and installed a count of Malta in 1192. As the islands were much desired due to their strategic importance, it was during this time that the men of Malta were militarised to fend off attempted conquest; early Counts were skilled Genoese privateers.