Церковь призывала христианских правителей прекратить междоусобные войны и обратить все силы против мусульман. Короли Западной Европы мало внимания обращали на её призывы, но многие представители знати воспользовались возможностью бежать от рутинных забот и отсутствия перспектив у себя на родине и отправиться на далекий, таинственный Восток в надежде обрести спасение души и власть.

Самым высокопоставленным из всех знатных людей, откликнувшихся на призыв к Крестовому походу, был герцог Нормандский Роберт II. Ему смертельно надоело бороться со своими баронами, с одной стороны, и со своим братом — с другой. Он не был правителем; он был военным авантюристом, а Крестовый поход сулил именно то, чего ему хотелось, — военные приключения и подвиги без каждодневной ответственности.

В 1095 г. Роберт объявил о своем намерении отправиться в Крестовый поход, и Вильгельм Рыжий согласился на перемирие. Поступи он иначе, он вызвал бы недовольство папы и восстановил против себя общественное мнение Европы. Кроме того, было очень заманчиво избавиться от Роберта, отправлявшегося в поход, из которого он, возможно, и не вернётся, и прижимистый Вильгельм даже соизволил одолжить брату десять тысяч марок под залог его владений. Несомненно, Вильгельм от всей души желал Роберту злой судьбы. Характерно, что эти десять тысяч он собрал со своих подданных в виде дополнительного налога, а не выложил из собственного кармана. Одо из Байе, не желая оставаться во власти Вильгельма, отправился с Робертом, но умер в пути, так и не достигнув Святой земли.

Роберт Коротконогий, разумеется, не был первым нормандцем, устремившимся на Восток. Его дед Роберт Дьявол шестьдесят лет назад совершил паломничество в Святую землю, и нормандские аристократы в таких паломничествах обычно останавливались в Италии, ибо вечная смута делала эту землю удобным местом для военных авантюр и получения новых владений.

Сицилию к тому времени уже два столетия удерживали мусульмане. Южная Италия была частью Византийской империи, которая теперь входила в период окончательного (но продолжительного) упадка.

В 1030 г. в южную Италию направились сыновья мелкого нормандского барона Танкреда де Отвиль, чьи владения располагались в сорока милях западнее Байе. Это была известная шайка буянов, и самым знаменитым среди них был Роберт, старший из семи сыновей Танкреда от второго брака (пять сыновей он имел от первого брака). Этот сын впоследствии стал известен под именем Роберт Гвискар, то есть Роберт Умный.

Старший сводный брат Роберта уже выкроил себе княжество в Апулии, на «мыске» Италии, а теперь и Роберт сделал то же самое в Калабрии, на «каблуке» Италии. В 1057 г., когда сводный брат умер, Роберт прихватил и Апулию, и к 1060 г. владения Византийской империи распространялись лишь на несколько укреплений в южной части полуострова. Всё остальное принадлежало Роберту.

Затем Роберт Гвискар обратил свои взоры к Сицилии: её завоевание он поручил своему брату Роджеру, младшему из двенадцати сыновей Танкреда, который присоединился к Гвискару в 1057 г. Роджер помог Гвискару разбить византийское войско в Калабрии, а в 1060 г. младший брат возглавил экспедицию на Сицилию. Он начал постепенное, но неуклонное завоевание острова, последовательно захватывая всё новые территории в течение двадцати лет.

Тем временем Роберт Гвискар в 1071 г. захватил Бари, последний византийский бастион в Италии. В 1081 г. он высадился на северо-западном побережье Балканского полуострова и начал продвигаться в глубь страны, теперь известной как Албания. Он вполне мог достичь Эгейского моря и занять большую часть Балканского полуострова, если бы ему не пришлось вернуться в Италию, чтобы защитить своего союзника папу.

Нормандцы в Италии на словах были преданными сторонниками папы, хотя на практике зачастую сражались против него. В то время папой был Григорий VII, который, ещё будучи монахом Гильдебрандом, поддержал герцога Вильгельма в его вторжении в Англию.