Как у папы, так и у его новых вассалов были причины быть довольными соглашением: «Папа обнаружил, что, признав нормандцев, он открыл для своей интервенции все районы юга Италии, находившиеся под их контролем. Нормандские лидеры позволили епископствам своих главных городов, Мельфи и Аверсы, перейти под прямое управление Рима… [Но] в 1059 году ни одна из сторон не могла предвидеть, что ждет их дальше. Краткосрочные практические выгоды [союза] были очевидны, но, скорее всего, обе стороны не задумывались над тем, насколько долговременным будет этот союз». Действительно, имея дело с таким правителем, как Роберт Гвискар, умело сочетавший военную силу с искусством дипломатических комбинаций, сложно было рассчитывать на какие-либо гарантии. В свою очередь, на папский престол вскоре взошел Григорий VII, талантливый, но фанатичный реформатор, не склонный к политическим компромиссам. В результате на протяжении десятилетий взаимоотношения нормандцев и Рима были очень непростыми. Но после разрыва в 1070-е годы, когда папа Григорий даже отлучил Гвискара от церкви, союз был восстановлен, а в 1084 году, спасая папу от его главного врага, императора Генриха IV, Роберт захватил, разграбил и сжег Рим — так, как Вечный город не разорял никто со времен вандалов в V веке.
Византийская принцесса Анна Комнина в своем труде «Алексиада», посвященном жизни ее отца, императора Алексея I (правил в 1081-1118), оставила описание внешности и характера Роберта Гвискара, который производил большое впечатление даже на своих противников: «Роберт… был выдающимся полководцем, обладал острым умом, красивой внешностью, изысканной речью, находчивостью в беседе, громким голосом и открытым нравом. Он был высокого роста, всегда с ровно остриженными волосами на голове и с густой бородой. Роберт постоянно стремился блюсти нравы своего племени и до самой кончины сохранял свежесть лица и всего тела. Он гордился этими своими качествами; благодаря им его внешность могла считаться достойной владыки. Он с уважением относился ко всем своим подчиненным, а особенно к тем, которые были наиболее ему преданы. В то же время Роберт был очень скуп, корыстолюбив… да к тому же чрезвычайно тщеславен». Как сказали бы сегодня, это портрет харизматического лидера — и нет оснований удивляться тому, что Роберту Гвискару удалось сделать столь выдающуюся карьеру.
С 1060 года в истории нормандской экспансии в Италии открывается новая глава — пришельцы переправляются через Мессинский пролив и начинают завоевание Сицилии, уже пару веков принадлежавшей арабам. Любому, кто рассчитывал тогда закрепиться в Центральном Средиземноморье и обладать там военно-политическим и экономическим влиянием, без Сицилии было не обойтись. «Положение Сицилии, отделенной в одном месте лишь двумя милями от Италии и менее чем ста милями от Африки, сделало остров опорным пунктом между Европой и Африкой и водоразделом, делящим Средиземноморье на восточную и западную части». Кроме того, нормандская экспансия к тому времени приобрела свою логику, которая также подталкивала этих выходцев с севера к покорению острова: «Сицилия, зеленая и плодородная, лежащая едва ли в трех или четырех милях от материка, была не только очевидной целью и естественным продолжением того великого продвижения на юг, которое привело норманнов из Аверсы к южным границам Калабрии; она являлась логовом сарацинских пиратов, чьи набеги… постоянно угрожали прибрежным городам юга и запада. Пока Сицилия оставалась в их руках, как мог герцог Апулии обеспечить безопасность своих вновь утвержденных владений?»
У Гвискара было полно забот как в Апулии, так и в более далеких краях — на греческом побережье, куда к концу жизни старый герцог распространил свою экспансию. Роберт воевал почти непрерывно — то с мятежными соплеменниками, то с соседними лангобардскими князьями, то с византийцами. В Калабрии же и особенно на Сицилии все большим влиянием пользовался его младший брат Рожер (по возрасту скорее годившийся Гвискару в сыновья), который ловко использовал распри между арабскими эмирами на острове. Нормандцев было по-прежнему мало — Рожер редко выступал во главе войска, насчитывавшего более 3-4 тысяч воинов. Но они сражались искусно, а после того, как Рожер первым среди нормандских предводителей стал использовать осадную технику, сицилийские города начали сдаваться ему один за другим. К тому же местное население, значительную часть которого составляли греки, жившие на Сицилии с античных времен, испытывало к нормандцам — хоть и латинянам, и свирепым варварам, но все же христианам — определенные симпатии.
В самом начале 1072 года войско Рожера взяло Панормус (Палермо). И хотя для полного завоевания Сицилии ему понадобилось еще почти два десятилетия, «великий граф» — таков отныне был титул Рожера I — стал хозяином положения на острове. Определенные позиции сохранились за ним и в Калабрии, которую он фактически разделил со старшим братом. Гвискар, которому было уже под 70, умер в 1085 году во время очередного похода в Грецию, оставив свои владения на юге Италии в руках своего сына Рожера, прозванного Борсой («Кошельком») за привычку часто пересчитывать монеты в мошне. После этого влияние графа Рожера Сицилийского возросло еще больше: его молодой тезка был правителем довольно слабым, к тому же непрерывно враждовал со старшим братом Боэмундом, лишенным наследства после того, как церковь признала недействительным первый брак Гвискара — с матерью Боэмунда. Граф Сицилийский то и дело выступал в роли посредника между Рожером Борсой и Боэмундом, постепенно становясь фактическим правителем юга Италии.