Однако на политическом горизонте быстро сгущались тучи. Через месяц после коронации Алексея герцог Апулии Роберт Гвискар начал масштабное наступление на Римскую империю.
История норманнов на юге Италии началась около 1015 года с группы молодых нормандских пилигримов, которых правитель лангобардов уговорил стать наемниками в войне против византийцев. Слух об этом вскоре дошел до Нормандии, и первый ручеек свободных младших сыновей, странствовавших в поисках богатства и приключений, быстро разросся до масштабов устойчивой иммиграции. Вскоре они стали брать плату за свои услуги, и в 1053 году в битве при Чивитате в Апулии разбили сильно превосходившую их армию, которую собрал и лично повел против них папа Лев IX.
К этому времени власть находилась в руках семьи некоего Танкреда де Готвиля, малоизвестного рыцаря, служившего герцогу Нормандии. Восемь из его двенадцати сыновей обосновались в Италии, пятеро стали первоклассными командирами, а один – Роберт по прозвищу Гвискар («Хитрец») – был почти гением. После битвы при Чивитате политика римского престола изменилась, и в 1059 году Роберт получил от папы Николая II прежде не существовавшие герцогства – Апулию, Калабрию и Сицилию. Два года спустя Роберт и самый младший его брат Роджер вторглись на остров и в течение следующих десяти лет продолжали оказывать давление и на Сицилии, и на материке. Бари пал в 1071 году, а вместе с ним и остатки византийской власти в Италии; в начале следующего года за ним последовал Палермо, и сарацинское влияние на Сицилии закончилось навсегда. Четыре года спустя настала очередь Салерно – последнего независимого княжества лангобардов. Верховная власть во всей Италии к югу от реки Гарильяно отныне принадлежала Роберту Гвискару и его норманнам.
Эта территория уже многие века была известна как Великая Греция, и тогда по духу она была больше греческой, нежели итальянской. Для большинства ее жителей греческий был родным языком, греческие обряды преобладали почти во всех храмах и в большинстве монастырей. Неудивительно, что Гвискар начал вынашивать замыслы об овладении императорским троном, и их невольно поощряли сами византийцы. В 1074 году Михаил VII предложил своего сына Константина в качестве будущего жениха для самой красивой из дочерей Роберта (он особо уточнил эту деталь). Гвискар не колебался: нельзя упускать возможность стать тестем византийского императора. Он принял это предложение и вскоре после этого отправил свою дочь Елену в Константинополь, где она жила и училась на женской половине императорского дворца в ожидании, пока ее жених-младенец достигнет брачного возраста.
Свержение Михаила VII в 1078 году уничтожило все шансы Елены на императорский трон. Злополучную принцессу заключили в монастырь, что, несомненно, совершенно ее не обрадовало. Ее отец принял эти известия со смешанными чувствами. Его надежды на обретение зятя-императора разбились, но обращение с его дочерью давало отличный повод для вторжения. Летом 1080 года Роберт Гвискар начал подготовку. Империя все глубже погружалась в хаос, и в нынешнем ее состоянии хорошо спланированное нападение нормандских воинов имело все шансы на успех.
Подготовка продолжалась всю осень и зиму. Ремонтировали флот, наращивали численность армии и заново ее экипировали. В попытке пробудить воодушевление среди своих греческих подданных Гвискар даже умудрился предъявить им сомнительного и явно фальшивого православного монаха, который появился в Салерно в разгар приготовлений и выдавал себя не за кого иного, как за самого Михаила VII, сбежавшего из ссылки и доверившего своим благородным нормандским союзникам заменить его на троне. Никто ему особо не верил, но Роберт утверждал, что полностью верит его заявлениям, и на протяжении следующих нескольких месяцев упорно обращался с ним с преувеличенным почтением.
Узнав о совершенном Алексеем перевороте, он отказался менять планы. К тому времени он утратил всякий интерес к брачным связям с императорской семьей, но меньше всего на свете желал возвращения Елены: у него было еще шесть дочерей, и Елена была гораздо полезнее, находясь в Византии. Для него сомнительный монах по-прежнему был императором Михаилом, законным правителем Византии. Теперь было важно начать наступление прежде, чем Алексей вернет ему Елену. Роберт уже отправил своего старшего сына Боэмунда через Адриатику во главе передового отряда, и чем скорее он сам сможет к нему присоединиться, тем лучше.