Между тем с началом XI в. в Южной Италии подготовляются события чрезвычайной важности: с одной стороны, назревало разрешение сарацинского вопроса, который черпал свою силу в притязаниях двух империй на господство в Южной Италии, с другой — приближался кризис в борьбе папства и императора. Хотя со времени катастрофы, постигшей германское войско в 982 г., Византия имела полный досуг укрепиться в Апулии и Калабрии и раздвинуть свои притязания до Кампании, тем не менее среди части населения Южной Италии не умирало желание стряхнуть зависимость от Византии, в особенности это заметно было в городах, где еще были живы национальные тенденции лангобардской аристократии. В 1008 г. при катепане Куркуа вспыхнуло восстание под предводительством некоего Мели, знатного жителя города Бари. Так как вместе с этим восстанием ставится в связь начальный факт участия норманнов в делах Южной Италии, то восстанию под главенством Мели приписано в истории, может быть, больше значения, чем оно того заслуживает. В самом деле, по существу это было довольно обыкновенное выражение протеста, какие нередко бывали в больших городах. Хотя усмирение мятежа было не так легко и сопровождалось неоднократными вооруженными столкновениями, в которых на стороне горожан были и сарацины, тем не менее перевес оказался на стороне катепана Василия Аргира, или Месардонита. Мели вместе со своим шурином Датто успел спастись бегством в лангобардские города и нашел убежище в Капуе. Это происходило в 1009 и 1010 гг. Завладев Бари, катепан принял меры к подавлению движения, нашедшего отражение и в других городах Апулии. Он посетил Салерно в октябре 1011 г., по всей вероятности, с целью выяснить, где находится Мели, который скрывался в это время близ Беневента. Между тем шурин его ушел далее на север и поступил на службу к папе Бенедикту VIII, который доверил ему защиту укрепления на берегу Гарильяно близ Гаэты. Из этих данных можно до некоторой степени понять, откуда могло иметь поддержку антигреческое движение в Южной Италии. Когда и кто поставил Мели в сношения с норманнами, это остается не совсем ясным.
По одной версии, в первый раз соглашение с норманнами насчет изгнания греков из Италии состоялось в Капуе, по другой версии, сохранившейся у Вильгельма Апулийского (12), первое знакомство состоялось на горе Гаргано, в монастыре св. Михаила, где норманны были в качестве пилигримов на возвратном пути из Иерусалима. Мели рассказал им историю своей попытки и так подействовал на воображение норманнов картиной легкого успеха, какого они могут достигнуть в занятой греками стране, что они будто бы дали ему слово по прибытии на родину набрать охотников и снова вернуться в Италию (13). Наконец, существует еще предание, что норманны в своих путешествиях в Иерусалим имели случай ознакомиться с положением дел в Южной Италии и раз оказали помощь герцогу Салернскому в его борьбе с сарацинами, после чего охотники из норманнов нередко появлялись в Италии с предложением своих услуг.
Во всяком случае первая партия норманнских охотников с Гислербертом во главе появляется в Капуе в 1015 или 1016 г. Весьма вероятно, что по указаниям папы Бенедикта VIII они направлены были сначала на помощь к герцогу Салернскому против сарацин и, когда эта задача была исполнена, по внушениям того же папы вошли в сношения с вышеупомянутым Мели и приняли участие в антивизантийском движении, которое было одинаково полезно и для папы, и для лангобардских князей. Новейший исследователь этого эпизода (14) такими словами определяет роль норманнов: