Карл был в Неаполе, когда в начале апреля посланник архиепископа Монреальского сообщил ему о резне в Палермо. Карл пришел в ярость, поскольку это означало, что придется отложить поход на Константинополь на некоторое время, но поначалу он не воспринял восстание всерьез. Карл решил, что это локальные волнения, с которыми его наместник, Герберт Орлеанский, вполне может справиться. Карл лишь приказал вице-адмиралу Маттео Салернскому взять четыре галеры и атаковать Палермо. Этот приказ был отдан 8 апреля, но, добравшись до Палермо, Маттео обнаружил на подходе к гавани мессинскую эскадру и не решился напасть на нее. Когда Мессина присоединилась к восстанию, мессинские корабли атаковали Маттео и захватили две его галеры. С оставшимися кораблями он отступил в Неаполь.295

Мятеж в Мессине и разгром его флота привели Карла к осознанию серьезности восстания. «Господь Всемогущий! — воскликнул он. — Если Тебе угодно низвергнуть меня, позволь мне хотя бы спускаться вниз мелкими шагами». И Карл стал принимать меры для того, чтобы шаги оказались мелкими. Поход на Константинополь был отменен. Вместо этого корабли и солдаты, собравшиеся в портах Италии, были стянуты к Мессинскому проливу, и сам Карл выступил во главе армии, которая должна была подавить мятеж на острове.296

Папа полностью поддерживал Карла. Когда в апреле в Орвьето прибыл посланник из Палермо, чтобы просить Святейший Престол взять под свое покровительство новую коммуну, Папа Мартин отказался дать ему аудиенцию. На острове все же надеялись, что Мартин еще смягчится. В начале мая Мессина вместе с Палермо и другими городами отправили троих послов к папскому двору. Они торжественно вошли в его приемную и предстали перед всей консисторией, трижды пропев слова: «Агнец Божий, искупивший все грехи мира, смилуйся над нами». Но Папа ответил с горечью, трижды повторив слова Евангелия: «Радуйся, Царь Иудейский! — и били Его». Другого ответа посольство от Папы не получило.297 Вместо этого 7 мая, на Вознесение, Папа издал буллу об отлучении мятежных сицилийцев и всех, кто поддержит их. Второй буллой он отлучил Михаила Палеолога, «называющего себя греческим императором», а третьей — Гвидо да Монте-фельтро и гибеллинов Северной Италии.298

У Карла был еще один друг — его племянник, французский король Филипп. В апреле Карл написал ко французскому двору, сообщая Филиппу, что, возможно, понадобятся активные действия, чтобы предотвратить серьезные последствия мятежа. Когда Мессина восстала, Карл снова написал, прося помощи против бунтарей. В ответ двое его племянников — Филипп и его брат Пьер, граф Алансонский — и Роберт д'Артуа решили во главе отряда французских дворян отправиться в Италию. Сын Карла, Карл Салернский, находившийся в то время в Провансе, был направлен в Париж с тем, чтобы организовать дальнейшее сотрудничество с французским двором.299 Король Филипп считал, что главная опасность исходит от Арагона. Он уже предупреждал Карла, чтобы тот остерегался короля Арагонского, но Карл не послушал его. Филипп был убежден, что огромный арагонский флот, собравшийся в гавани в устье реки Эбро, готовится к атаке на Сицилию, несмотря на все заверения короля Педро в том, что он собирается в крестовый поход в Африку. Еще не зная, что Мессина потеряна для Карла, Филипп отправил посольство к королю Педро, который уже присоединился к своему флоту. Послы достигли устья Эбро 20 мая и передали Педро письмо, в котором Филипп требовал гарантий того, что флот Педро не нападет против Карла. Если же это все-таки случится, Филипп предупреждал, что будет расценивать это как враждебный акт и двинет свою армию против Арагона.300

Предупреждение Филиппа не возымело никакого действия. Педро, как всегда, ответил, что он готовится к походу в Африку. На самом деле мятеж на Сицилии застал Педро врасплох. Его агенты планировали это восстание, но он рассчитывал выждать до того времени, когда Карл пойдет войной на Константинополь. Когда из Сицилийского королевства уедут лучшие воины Карла, там и должны были поднять восстание; в этот момент Педро намеревался вмешаться. Сицилийцы, получившие стимул от византийского императора, опередили его. Получив известие о резне в Палермо, Педро не предпринял ничего. Лишь после восстания в Мессине и уничтожения кораблей Карла он решил действовать. И даже тогда он соблюдал осторожность. Он действительно решил отправиться в Африку сражаться с маврами, ожидая дальнейшего развития событий на Сицилии. 3 июня Педро вышел в море во главе огромной флотилии военных и транспортных кораблей, направляясь к алжирскому побережью.301

Чтобы подтвердить свою легенду, Педро отправил специального посла к Папе с просьбой благословить его крестовый поход и даровать обычные в таких случаях индульгенции. Но Мартина он не обманул. Тот довольно резко ответил послу. Швейцарский рыцарь Отто де Грансон, бывший агентом Эдуарда Английского в Орвьето, 11 июня доложил своему патрону, что все при папском дворе ожидают вторжения короля Арагонского на Сицилию.302 Но Педро не торопился. Его флот зашел в Порт Магон на острове Менорка, который все же был мусульманским эмиратом, хоть и подчиненным арагонской короне. Эмир поспешил обеспечить флот щедрыми запасами провизии, но отправил тайного посланника в Тунис, чтобы предупредить Тунисского эмира о походе. Когда флот прибыл в Колло, расположенный на алжирском побережье, Педро узнал, что его союзник, правитель Константины, ради чьей независимости от тунисского эмирата и его обращения в христианскую веру и затевался крестовый поход, был внезапно атакован тунисцами, предупрежденными посланником с Менорки, и убит. Его смерть лишила поход основной цели. Но Педро остался с солдатами в Колло, в достаточной близости от Сицилии, чтобы следить за тем, как будут развиваться события.303

Сицилийцы тем временем готовились отразить нападение короля Карла. Карл же не спешил. Он хотел нанести удар наверняка. Его корабли и воины, предназначавшиеся для похода в Константинополь, были собраны в Катоне на калабрийском побережье пролива. Пьер д'Алансон и Роберт д'Артуа вместе со своими французскими рыцарями вскоре должны были присоединиться к армии Карла Анжуйского. Численность войска была увеличена за счет солдат из Прованса — из той армии, которая должна была отправиться вверх по Роне, чтобы возродить Арелатское королевство. Гвельфы Флоренции прислали отряд под предводительством графа Гвидо да Баттиффолья со знаменем города и пятьюдесятью молодыми флорентинцами, которых король Карл обещал посвятить в рыцари. Взамен кораблей, уничтоженных мессинцами, были наняты корабли из Венеции, Пизы и Генуи. Это была грозная армия, которую 6 июня возглавил сам король Карл. Девятнадцать дней спустя он вместе с армией переправился через пролив и встал лагерем среди виноградников прямо к северу от Мессины.304

Папа Мартин надеялся, что сицилийцы испугаются и подчинятся без боя. Они же продолжали утверждать, что их коммуны находятся под покровительством Папы. 5 июня Папа назначил одного из своих самых искусных советников, кардинала Герарда Пармского, легатом на остров с указаниями добиться от сицилийцев безоговорочной капитуляции.305 Пять дней спустя король Карл в поддержку усилий Папы издал большой эдикт, реформирующий управление островом. Королевским чиновникам впредь запрещалось вымогательство в какой бы то ни было форме; запрещалось конфисковать товары, скот или корабли безвозмездно; принуждать города и деревни преподносить им дары; заключать сицилийцев в тюрьму на недостаточных основаниях; присваивать их земли. В этом эдикте Карл, таким образом, признавал, что в дни, предшествовавшие восстанию, эти злоупотребления имели место.306 Но обещание этих реформ оставило сицилийцев равнодушными. Они слишком много претерпели от правления Кар-ла Анжуйского, и их гордость пробудилась: они были готовы бороться. 2 июня мессинцы уже расстроили попытку анжуйской армии высадиться в Милаццо, на северо-восточном побережье острова. Их дух не был сломлен, когда три недели спустя один из отрядов Карла Анжуйского все же осуществил там высадку и разбил, нанеся тяжелые потери, пытавшееся его отбросить мессинское ополчение. Единственным следствием разгрома мессинцев стало то, что они ворвались в цитадель, где содержали в заточении членов семьи Ризо, и убили их; они также сняли судью Балдуина Мюссоне с поста капитана, посчитав его некомпетентным и бездеятельным. На его место избрали Аламо да Лентино, одного из тех троих сицилийских аристократов, которые играли главную роль в заговоре Джованни да Прочиды. Он оказался более энергичным лидером, чьим единственным недостатком была его зависимость от жены, Махальды да Скалетта, женщины скромного происхождения и огромных амбиций.307 В тот момент супруга была не с ним — она отправилась со своими вассалами в Катанию, где хитростью заставила перепуганных солдат французского гарнизона сдаться на ее милость и всех их приказала перебить, взяв власть в городе в свои руки.308