3 июля Карл добился нового дипломатического успеха: в этот день в Орвьето в Центральной Италии он подписал договор о военном союзе с Венецианской республикой. Соглашение, под которым также стояла подпись Филиппа де Куртенэ, титулярного императора Константинопольского и зятя Карла Анжуйского, предусматривало совместную подготовку похода на греческую столицу. Сицилийский король обеспечивал сухопутные силы (8 тысяч конных рыцарей и пеших воинов) и транспортную флотилию для их переправы, Венеция же предоставляла 40 боевых галер для защиты этого войска и борьбы с византийским флотом. В обмен венецианцам было обещано восстановление всех привилегий, которыми они пользовались в Константинополе при латинских императорах. Начать операцию планировалось не позднее апреля 1282 года. Предполагалось также возобновление активных боевых действий на западе Балканского полуострова: с этой целью не позднее 1 мая 1282 года на острове Корфу должна была сконцентрироваться вспомогательная флотилия союзников. Туда должен был быть переброшен отряд из 300 тяжеловооруженных рыцарей, нанятых Карлом; их целью было подкрепить ослабленные недавним поражением при Берате (1281; см. главу V) войска короля на Балканах. Судя по всему, речь шла о том, чтобы отвлечь значительные силы греков и не позволить им собрать все войска для обороны Константинополя. Карл и венецианцы рассчитывали также на помощь эпирского деспота Никифора Комнина, противника Михаила VIII.

Для византийского императора подобные планы неожиданностью не были. После разгрома анжуйского войска при Берате Палеолог чувствовал себя довольно уверенно, но прекрасно понимал, что Карл не отступится от своих планов разгрома его империи. Избрание нового папы и его, Михаила, отлучение от церкви, последовавшее 18 октября 1281 года, показали василевсу, что на сей раз компромисса с латинянами, видимо, достичь не удастся. Более того, образовавшаяся коалиция Regno, Венеции и папства выглядела грозной как никогда. Палеолог остро нуждался в союзниках. Наиболее естественным партнером выглядел Педро III Арагонский, чья враждебность по отношению к Карлу была хорошо известна. Более того, ряд источников — в частности, хроника Сабы Маласпины и арагонские документы, опубликованные еще в конце XIX века итальянским историком Карини, — свидетельствуют о том, что Педро предпринимал военно-дипломатические усилия по подрыву власти Карла в Regno задолго не только до «Сицилийской вечерни», но и до формального соглашения с Византией, достигнутого в конце 1281 года и направленного против Карла. (Об этом договоре упоминает другой хронист — Бартоломео из Лукки, впоследствии секретарь папской курии.)

При арагонском дворе уже давно жила большая группа изгнанников из Regno, потерявших свои владения либо после гибели Манфреда, либо после поражения Конрадина. Эти люди, среди которых выделялся уже упоминавшийся кондотьер-флотоводец Рожер (Руджеро) ди Лауриа, служили королеве Констанции, дочери Манфреда и супруге Педро III, как своей законной государыне, надеясь на свержение анжуйского режима и установление власти Барселонского дома, в котором они видели преемника Гогенштауфенов. Другой важной фигурой в этом, как выразились бы сегодня, эмигрантском кругу был врач и некогда состоятельный землевладелец родом из Салерно по имени Джованни да Прочида. Это был уже весьма немолодой человек (большинство источников указывают, что он родился в 1210 году), успевший послужить в качестве придворного лекаря Фридриху II, Конраду IV и Манфреду. Джованни да Прочида был весьма образован, говорил на множестве языков и перевел на латынь ряд арабских медицинских трактатов. Он владел многочисленными поместьями в окрестностях Неаполя, пожалованными ему Гогенштауфенами. Успешная карьера этого человека, однако, прервалась в 1269 году, когда Карл Анжуйский лишил его всех владений, обвинив в поддержке Конрадина, чему имелось немало доказательств. Джованни бежал вначале в Венецию, затем в Барселону. «Говорили, что с его женой дурно обошлись, одна из его дочерей была изнасилована, а один из сыновей — убит наглым французским рыцарем, явившимся, чтобы изгнать семью из их дома». Если дела в действительности так и обстояли, у Джованни было более чем достаточно оснований для глубокой ненависти к Карлу Анжуйскому и желания отомстить ему.

За Джованни да Прочидой закрепилась репутация главы заговорщиков, подготовивших почву для «Сицилийской вечерни». К 1280 году он занимал при арагонском дворе высокий пост канцлера. Однако историки расходятся во мнениях относительно того, действительно ли Джованни находился в самом центре паутины, соединившей двор в Барселоне с Константинополем, итальянскими противниками Карла Анжуйского и немногочисленными гибеллинами, остававшимися в самом Regno. По мнению Стивена Рансимена, Джованни «контролировал внешнюю политику короля [Педро]». Джин Дюнбабен, однако, полагает, что Прочида «был далеко не единственным агентом, вовлеченным [в организацию заговора], и его прямое влияние на Педро, вероятно, имело большее значение, чем его [дипломатические] интриги». Хроника Lu Rebellamentu di Sichilia («Восстание Сицилии»), чья достоверность в изложении фактов, связанных с «Сицилийской вечерней», часто подвергалась сомнению, является главным источником, на основании которого за Прочидой закрепилась репутация героя, подготовившего патриотическое восстание. Согласно этой хронике, Джованни добрался даже до Константинополя, где провел несколько месяцев и был принят Михаилом VIII, с которым обсуждал детали заговора против короля Карла. Двигателем всей комбинации он считал Прочиду и Джованни Виллани.

Современные историки, однако, относятся к этим сведениям скептически: «…Прочида не играл главной посреднической роли, приписываемой ему Виллани. Ведь документы, несущие его подпись, доказывают, что в то время, когда он якобы находился в Константинополе, на Сицилии или в папской курии, в действительности он подписывал официальные бумаги в Арагоне… Он мог в это время совершить пару поездок, но… его роль в подготовке “Сицилийской вечерни” была более ограниченной и заключалась главным образом в переговорах с сицилийскими баронами». Эти бароны — неважно, через самого Джованни или других арагонских эмиссаров, которыми могли быть, по разным данным, сыновья этого хитроумного врача-дипломата, — заверяли Педро III и его супругу в своей преданности и призывали их покончить с анжуйским правлением. В числе заговорщиков источники называют, в частности, видных нобилей Regno — Пальмьери Аббате, Алаймо Лентини и Гуальтерио ди Кальтаджироне.

Некоторые современники считали, что к подготовке заговора был причастен в последние месяцы жизни даже папа Николай III. Салимбене де Адам прямо утверждает, что папа «с согласия некоторых кардиналов, входивших тогда в курию, отдал [Сицилию Педро Арагонскому] из ненависти к королю Карлу». В этом, впрочем, тоже есть обоснованные сомнения: «Конечно, [папа Николай] не слишком жаловал Карла, к тому же он был алчен и был бы рад денежному преподношению[178] от [византийского] императора. Но целями его политики являлись умиротворение, независимость папских Владений и обогащение клана Орсини. Ни в одном из папских документов того времени нет и намека на то, что понтифик обдумывал устранение Карла с сицилийского трона и его замену Педро Арагонским». Но «Михаил Палеолог, тем не менее, посылал “греческое золото” Педро и антианжуйски настроенным кардиналам (если не самому папе Николаю III), что подтверждается несколькими греческими и латинскими источниками». Они, в частности, называют имя генуэзца Бенедетто Захарии, который служил посредником и финансовым курьером между Византией, Арагоном и своей родной Генуей (которая была сильно обеспокоена союзом Карла I со старой соперницей генуэзцев — Венецией). К началу 1282 года «Альфонсо [X Кастильский], Педро Арагонский, Гийом Монферратский[179] и Генуя — все они, в той или иной степени, находились в дипломатическом контакте с Палеологом».