Гвискар уже обладал графским титулом, но его действиям пока не хватало размаха. И ему снова повезло: скончался его брат Онфруа. Нормандцы, смутно помнившие тинги предков-викингов, избрали Роберта правителем по праву самого сильного и бесстрашного. А в 1059 году он получил от папы титул короля Сицилии. Проблема была в том, что фактически остров принадлежал арабам, и его предстояло захватить. Папская грамота возводила войну за новые земли в ранг крестовых походов — каждому, кто приходил на помощь Гвискару, автоматически отпускались грехи. Нормандцы из варваров и грабителей вдруг превратились в ревностных вассалов папы и так переусердствовали, насаждая латинские обычаи среди греков, что спровоцировали раскол христианской церкви на католическую и православную.
Но перед тем, как отправиться на захват Сицилии, северяне получили ещё один полезный навык. Во время осады одного из последних бастионов византийцев, крепости Реджо, они обучились строительству осадных машин. Тут в истории Гвискара появляется важный персонаж — его младший брат Рожер. Такой же бесстрашный и амбициозный, он станет ещё одним великим Отвилем, едва не затмив Роберта. Именно его потомки будут королями Сицилии и Южной Италии. Но в 1060-м Рожер был просто подопечным Роберта, ответственным за метательные орудия. И при осаде Реджо он блестяще себя проявил.
А в 1061 году случились две вещи, которые убедили Гвискара в том, что завоевания Сицилии от него добивается Господь. Во-первых, стало ясно, что нормандцы не могут жить без битв. Как только закончились войны, в их рядах начались брожения. Северянам нужна была великая идея, иначе из подданных они превращались в угрозу. Во-вторых, один из эмиров Сицилии, Ибн ат-Тимнах, лично прибыл ко двору Гвискара просить его о помощи. В награду за уничтожение других эмиров он предложил владение всей Сицилией.
Завоевание этого по-восточному изобильного и полного сокровищ острова оказалось одной из самых ярких страниц в истории нормандцев, наравне с завоеванием Англии. Но ни Роберт, ни Рожер не ожидали, что война займёт 31 год. Сарацины оказались крепче, чем греки и лангобарды, и в религиозном фанатизме им не уступали.