Вскоре после этого Педро III свернул лагерь и в конце августа погрузил свою армию на корабли. По словам Рамона Мунтанера, численность королевских войск, с момента прибытия к алжирскому побережью, значительно увеличилась. Корабли с подкреплениями прибывали из Каталонии почти ежедневно[363]. Хронист оценивает численность пехоты как минимум в 40.000 человек,[364] но Марино Санудо Торселло предлагает более убедительную цифру в 8.000 альмугаваров и 600 рыцарей,[365] которые, по подсчётам Джованни Аматуччо, прибыли примерно на 30–50 кораблях, из которых 22 были боевыми галерами[366]. Флот отплыл из Северной Африки около 25 августа и прибыл в Трапани 30-го, где был с ликованием встречен жителями города. Из Трапани Педро III по суше отправился к Палермо, а флот под командованием Рамона Маркета следовал за ним минуя мыс Сан-Вито и залив Кастелламмаре. Арагонский король вошёл в город 2 сентября — в тот же день, когда Карл предпринял очередную безуспешную атаку на Монте-делла-Каперрина. Педро III встретили звуками труб и восторженными криками толпы, словно он был победителем-цезарем, возвращающимся в Рим для своего триумфа. 4 сентября, повторив своё обещание править по образцу нормандских королей древности, Педро III был провозглашен королем Сицилии собравшейся в Палермо знатью[367].

На военном совете все согласились, что первоочередной задачей должна стать деблокада осажденной Мессины[368]. С этой целью было решено привлечь местное ополчение. По словам Берната Десклота, сицилийцы были крайне обескуражены потрепанной армией Педро III, прибывшей после трудной африканской кампании:

И поскольку рыцари и альмугавары  прибыли в Палермо в порванных и пропитанных потом одеждах, потемневших доспехах, смуглыми от солнца, жители Палермо сочли их малополезными, в глубине души считая, что такие люди никогда не смогут вырвать их из рук Карла, столь могущественного на суше и на море[369].

Поэтому, одним из первых начинаний Педро III как короля Сицилии стало издание прокламации, предписывающей всем сицилийским мужчинам в возрасте от 15 до 60 лет собраться в Палермо в течение 15 дней, имея при себе месячный запас провизии[370].

Затем, ожидая прибытия своих войск из Трапани и сбора ополчения со всей западной Сицилии в Палермо, Педро III отправил посольство в Мессину. Делегация, состоявшая из арагонских рыцарей Педро де Керальта и Руиса Эксименеса де Луны, а также магистрата из Барселоны по имени Гильем Аймерих, должна была сообщить Карлу Анжуйскому, что, поскольку по воле всего народа король Арагона занял сицилийский трон от имени Констанции Гогенштауфен, он должен немедленно покинуть остров[371]. Вскоре после этого Педро III двинулся в путь во главе всей собранной армией, через Никосию и Троину (в северной части острова), в то время как его флот плыл на восток вдоль северного берега к Мессинскому проливу, чтобы перерезать сообщение Карла с Калабрией (Карта 6). Ранее он отправил сообщения с приказом всем остальным ополченцам идти на соединение с ним в Рандаццо (на северных склонах Этны, примерно в 65 км к юго-западу от Мессины)[372]. Возможно, ещё более важным стало то, что Педро III приказал авангарду двинуться вперёд и ночью прорваться в город. Авангард состоял из 500 арбалетчиков с Балеарских островов под командование сицилийских изгнанников Никколо ди Палицци и Андреа да Прочида,[373] плюс — что наиболее важно — контингент из примерно 2.000 альмугаваров[374].

Альмугавары в Европе XIII века считались лучшей лёгкой пехотой. Происходя из неприхотливых пастухов-горцев Арагона и Каталонии, эти закалённые в боях пограничники жили за счёт набегов на приграничные районы Кастилии и Валенсии, населённые мудехарами (иберийскими мусульманами). Легко вооруженные и совершенно не имевшие доспехов, альмугавары во время сражений полагались на быстроту и ловкость. Они передвигались быстро и бесшумно, атаковали неожиданно, часто ночью и по пересеченной местности. Всё это делало их одновременно и страшными, и бесстрашными. Они не боялись даже кавалерии. Мунтанер рассказывает об одном эпизоде, когда отряд альмугаваров отбил конную атаку, поражая своими короткими копьями лошадей, а затем без труда перебив спешенных рыцарей своими длинными тесаками. Их название почти наверняка происходит от арабского слова almõgavar, означающего "разрушитель"[375]. Десклот предлагает наиболее точное из имеющихся описаний альмугаваров:

Эти воины, называемые альмугаварами, живут только ради войны, и живут они не в городах, а в горах и лесах. Они постоянно сражаются с сарацинами и совершают набеги на их земли в течение дня или двух, беря многих в плен, а также грабя их имущество, за счет которого они и существуют. Они терпят многие лишения, которые другие люди едва ли смогли бы вынести. Иногда они, если нужно, проводят по два дня без еды и питаются только полевыми травами, без всякого для себя вреда. Адалиды, являющиеся их вождями, прекрасно знают окружающие земли и дороги. Альмугавары носят лишь тунику или рубашку, летнюю или зимнюю, на ногах — кожаные штаны, а на ступнях — кожаные сандалии. У них на поясе толстый ремень с крепким клинком в ножнах. У каждого есть копье, два дротика и кожаный мешок для переноски провизии. Эти люди чрезвычайно сильны и быстры при преследовании, они каталонцы, арагонцы и сарацины (Илл. 3)[376].

Быстрота, выносливость и стойкость сделали альмугаваров идеальными для миссии, порученной им Педро III. "Хотя до города [Мессина] шесть дней пути, они добрались туда за три. — сообщает Мунтанер. — И вошли в город ночью, через место, называемое Каперрина… так тайно, что осаждающие их не услышали"[377]. Как и палермцы, мессинцы не были воодушевлены грубым видом своих потенциальных спасителей. По словам Мунтанера, некоторые из них говорили: "Мы не можем рассчитывать на большую помощь, если все воины короля Арагона такие как эти"[378]. Но такие настроения вскоре угасли. На следующий день альмугавары вырвались из ворот и застали осаждающих врасплох таким сокрушительным натиском, что, по словам Мунтанера, после этого более 2.000 анжуйцев лежали мертвыми или умирающими[379]. Что ещё более важно, этот эпизод послужил сигналом для Карла, что скорое прибытие короля Арагона со всей его армией неизбежно.

Бартоломео Неокастро утверждает, что Карл, возможно, был заранее предупрежден о высадке Педро III на остров двумя монахами-кармелитами, случайно встретившими арагонских посланников проезжавших через Никосию. Независимо от того, как он получил известие, к середине сентября Карл знал, что пока он всё ещё осаждает Мессину на него непременно нападут арагонцы, если только он не сможет взять город до их прибытия. Поэтому, 14 сентября он приказал начать полномасштабный комбинированный штурм города с суши и с моря[380].

На рассвете, анжуйцы продвинулись вдоль прибрежных равнин к северу и югу от города и с возвышенностей к западу, чтобы одновременно атаковать стены в нескольких места, используя все доступные средства и уловки. Требушеты обстреливали зубчатые стены и здания за ними, а тараны, называемые "кошками", били по башням, в то время как саперы пытались под них подкопаться. "Краны" опускали на стены штурмовые мостики, чтобы обеспечить нападающим доступ к машикулям (навесным галерея на консолях снаружи крепостных стен), а "аисты" поднимали над стенами платформы с бойцами, обрушивавшими на защитников болты и металлические пули из арбалетов. И, конечно же, к стенам были прислонены сотни лестниц по которым карабкались отважные пехотинцы[381].

Однако Алаимо да Лентини и его соотечественники не стали пассивными наблюдателями. Они с большим успехом использовали все доступные в то время средства обороны. Нападающих засыпали камнями и заливали кипящим маслом, а боевые машины поджигали горящей смолой. Те немногие французские бойцы, которым удалось пробиться на гребень крепостных стен, были встречены шквалом стрел и болтов из арбалетов и перебиты мечами и тесаками[382]. Микеле Амари дал наглядное описание ужасных последствий штурма: "У подножия стен образовался жуткий вал из сломанных машин и окровавленных и изувеченных трупов, окоченевших в судорожных позах смерти"[383].

В то же время, происходила ожесточённая битва за порт, закончившаяся с аналогичным результатом. Анжуйский флот, используя сильный попутный северный ветер, прорвался через укрепленный вход в гавань. В авангарде находился огромный, nave carica, вероятно, палубный парусный корабль, обычно используемый для перевозки грузов. Сопровождаемый боевыми галерами, он был покрыт шкурами, пропитанными уксусом в качестве огнезащитного средства, и снабжен мангонелями и требушетами. Двигаясь по ветру, он своей огромной массой должен был прорвать тяжелую цепь, преграждавшую доступ в гавань, но Алаимо, чтобы сорвать эту попытку, организовал мощную оборону. На берегу напротив оконечности мыса Браччо ди Сан-Райнери, окружающего гавань, он приказал построить деревянную бастиду и разместить там гарнизон. В самой гавани, за цепью, он выставил 14 галер с полными экипажами — шесть из которых были снабжены катапультами и баллистами. В центре находилась плавучая платформа, из двух связанных между собой тарид, с размещённой на ней боевой башней. За пределами цепи и чуть ниже поверхности воды были натянуты прочные сети в надежде запутать рулевые вёсла вражеских кораблей. Всё это блестяще сработало. Nave carica быстро запутался в сетях и встал, а мессинцы из бастиды и плавучей башни, обстреливали его палубу различными снарядами. Паруса были порваны, а экипаж частично истреблён, и корабль под градом камней из катапульт был вынужден отойти (предположительно, на буксире анжуйских галер)[384].

Карл наблюдал за всем происходящим с высот вокруг Санта-Мария-делле-Монаке, в районе нынешней церкви Санта-Мария-делле-Грацие, примерно в миле к западу от порта, когда некий мессинский капитан по имени Бонаккорсо навёл на него свою баллисту. К счастью для короля, двое рыцарей героически бросились перед ним, приняв на себя смертельный удар. Однако этот эпизод, очевидно, настолько его встревожил, что он приказал немедленно отступить. Когда разбитые осаждающие отступали, ликующие горожане вырвались из ворот и преследовали их до самого лагеря в посёлке Заэра, примерно в полутора милях к югу от города[385]. Тогда Карл осознал, что его последняя решительная попытка взять город провалилась. В отчаянии он попытался подкупить Алаимо, предложив ему великодушные условия: всеобщую амнистию для жителей Мессины (за исключением шести человек, которых Карл считал главными зачинщиками) и награду в 10.000 унций самому капитану, а также ежегодную пенсию в 200 унций и любой титул, который он мог бы потребовать. Капитан народа, теперь прославленный за вдохновенную защиту города, сразу же и с брезгливость отклонил это предложение[386].

Два дня спустя, 16 сентября, арагонские послы наконец-то добрались до анжуйского лагеря и на следующий день получили у короля аудиенцию. Карл, конечно же, решительно отверг притязания Педро III на королевство, но этот обмен заявлениями напомнил ему о неумолимом приближении арагонцев, что делало его положение у стен Мессины по меньшей мере бесперспективным[387]. Отпустив посланников Педро III, Карл созвал своих советников, чтобы обсудить альтернативные варианты. Некоторые решительные капитаны выступали за укрепление лагеря и организацию на западных холмах засады на арагонцев. Они хотели продолжать осаду до тех пор, пока не закончатся их запасы, рассчитанные ещё на два месяца. Однако более благоразумные, такие как графа Пандольфо ди Ачерра, указывали на то, что их неудачные попытки взять город привели к унынию в рядах анжуйской армии, а болезни и уход нескольких феодальных ополчений, отслуживших свой срок, значительно сократили её ряды. В любом случае, маловероятно, что анжуйцы преуспели бы в каких-либо будущих попытках, даже если бы их войска не понесли потери. Мессинцы — к тому времени получившие заверения о скором прибытии Педро III от генуэзского купца, видевшего короля на пути к городу, — оказали бы ещё более упорное сопротивление, зная, что их спасители уже в пути. Наконец, существовала вполне реальная вероятность того, что в Калабрии тоже вспыхнет восстание, оставив анжуйцев вообще без каких-либо подкреплений. Адмирал Карла, генуэзец, Арригино ди Мари, горячо поддерживал последнее опасение, добавив, что грозный арагонский флот и наступление зимней погоды могут сделать последующий отход невозможным. Более того, Карл считал свой собственный флот ненадежным, поскольку он в основном состояла из наемников[388]. У Карла не было выбора.

24 сентября он снял осаду Мессины и начал стратегическое отступление к Катоне с намерением возобновить кампанию весной. Операция началась достаточно гладко, с эвакуации осадных машин и самого короля, но переправа огромного количества людей со всеми лошадьми и снаряжением через пролив оказалась медленным и трудоемким процессом. Разноплемённость транспортного флота, состоявшего из пизанцев, венецианцев и генуэзцев, вероятно, только усугубила беспорядок и неразбериху. По-видимому, организация отхода заняла несколько дней. К концу операции (около 27 сентября) альмугавары, терпеливо выжидавшие за городскими стенами с момента той вылазки вскоре после их прибытия, увидели свой шанс. Они вырвались из ворот и набросились на французских рыцарей, отчаянно пытавшихся подняться на борт транспортных судов, убив по меньшей мере 500 из них[389]. Мунтанер настаивает, что было убито до 2.000 французов и что "более 150 галер и тарид" были подожжены: "И огонь был настолько сильным, что казалось, будто горит весь мир, а король Карл был очень огорчен, ибо он видел все это находясь Катоне"[390]. Так бесславно завершилась осада анжуйцами Мессины.

Как только последние анжуйские войска покинули остров, мессинцы послали гонцов, чтобы сообщить своему новому суверену, что город принадлежит ему. Они нашли Педро III в Рандаццо со всей его армией. Затем король двинулся на Милаццо, где вынудил анжуйский гарнизон капитулировать; и наконец, 2 октября, к безграничной радости жителей, Педро III вошёл в Мессину[391]. Три дня спустя, 5 октября, Педро III назначил Роджера ди Лаурия капитаном Августы — того самого портового города, жители которого пятнадцать лет назад были истреблены в ходе подавления предыдущего сицилийского восстания[392]. Роджеру суждено было стать тем врагом, который не позволил Карлу когда-либо снова ступить на Сицилию.