[[Fil:RogerReceivingTheKeysOfPalermo.JPG|left|thumb|240px|Hertug Robert og den nykårede grev Roger får nøglerne til [[Palermo]] i 1072.]]
I 1071 vendte Robert og hans hær tilbage til Scilien, og brødrene indledte en belejring af Palermo. I efteråret 1071 lykkedes det deres flåde at nedkæmpe en arabisk undsætningsflåde, og senere trængte den ind i byens havn og ødelagde den sicilianske flåde, så der ikke mere kunne blive tale om at få forsyninger fra søsiden. Byen var delt i to befæstede halvdele, og i januar 1072 lykkedes det Robert at erobre den ene halvdel, hvorefter resten af byen overgav sig. Roger havde været særdeles aktiv i kampene og som tak gav Robert ham store områder på øen (og ret til at erobre videre) og Roger fik titlen som greve af Sicilien, med Robert som sin lensherre. I de følgende år, frem til Roberts død i 1085, var Roger dog ikke i stand skaffe de fornødne penge og troppestyrker til en fortsat erobringskrig, men han gjorde dog fremskidt. I 1077 belejrede hans lille hær Trapani, der var et af de to tilbageværende arabiske støttepunkter på øens vestlige del. Hans søn Jordan stod i spidsen for et overraskelsesangreb på de tropper, der passede på byens græssende kvæg. Uden adgang til mad gav byen op snart efter. I blev 1079 Taormina belejret, og i 1081 stod Jordan i spidsen for en styrke, der i et nyt overraskelsesangreb erobrede [[Catania]], der hørte under emiren af Syracusa.
Kultur