Тогда же начали окончательно портиться отношения между королями: к Ричарду должна была прибыть невеста, и слухи об этом, видимо, дошли до Филиппа. В сопровождении королевы Алиеноры, которой было около 70 лет, приезжавшей за ней в Наварру, и присоединившегося по дороге графа Филиппа Фландрского Беренгария Наваррская в январе 1191 г. прибыла в Ломбардию. В это время там уже находился германский король Генрих, шедший за наследством жены в южную Италию. 20 января в Лоди близ Милана состоялась встреча королевы Алиеноры с королем Генрихом. В конце февраля кортеж старой королевы, молодой принцессы — невесты и графа Фландрского прибыл в Неаполь, и Ричард выслал несколько галер, чтобы доставить их в Мессину. Однако люди Танкреда разрешили взойти на борт только графу Филиппу. Алиеноре и Беренгарии поездка в Мессину была запрещена по причине многочисленности свиты и переполненности города.
Получив известие об этом, Ричард отправился к Танкреду за объяснением. Встретившись 3 марта в Катании, короли провели вместе пять дней. Опираясь на сообщение Роджера из Ховдена, можно нарисовать следующую картину. Танкред рассказал Ричарду, что Филипп предостерегал против него, уверял, что король Англии в нарушение договора планирует захватить его государство и, в случае войны, обещал помощь против Ричарда. В виде доказательства Танкред предъявил письма Филиппа, переданные ему герцогом Бургундским. Возможно, страх Танкреда мог быть усилен и многочисленностью свиты Алиеноры, и ее встречей с королем Генрихом.
Далее хронист рассказывает, что Ричард и Танкред расстались друзьями. В знак взаимного расположения Танкред подарил Ричарду четыре судна и пятнадцать галер. Со своей стороны, Ричард вручил Танкреду знаменитый Эскалибур, меч легендарного короля Артура, героя многочисленных поэм и рыцарских романов, недавно найденный при раскопках в аббатстве Гластонбери, на границе Уэльса.
Филипп стал жертвой своей нечестной игры. Взбешенный Ричард уклонился от встречи с ним. Французский король потребовал объяснений. Английский король представил объяснения через графа Фландрского. Филипп сначала смутился, потом все отрицал и заявил, что Ричард придумал это, чтобы оправдать отказ от брака с Алисой. Ричард отвечал, что он до последнего времени хотел жениться на Алисе, но теперь не может, так как недавно раскрылось, что Алиса была в связи со старым королем Генрихом и родила от него сына, о чем у него есть соответствующие документы и что могут подтвердить свидетели. Судя по тому, что граф Фландрский принял сторону Ричарда, оправдания Филиппа были не очень убедительными.
Чтобы избежать публичного скандала, Филипп освободил Ричарда от обручения. Был заключен договор, по которому Ричард передал Филиппу 10 тысяч марок, а приданое Алисы — город Жизор и нормандский Вексен — должно было принадлежать Ричарду и его мужским наследникам. Однако, если бы Ричард умер, не оставив наследника, Вексен должен был вернуться к Филиппу и его наследникам. 30 марта, за несколько часов до прибытия Алиеноры и Беренгарин, Филипп покинул Мессину и направился к берегам Палестины.
Алиенора привезла Ричарду новую невесту — Беренгарию. Проведя в Мессине три дня и отдав Беренгарию на попечение Иоанны, старая королева собралась в обратный путь вместе с архиепископом Руанским. Дела призывали их в Англию. Проезжая через Рим, они стали свидетелями событий мирового значения. 10 апреля 1191 г. умер папа Климент III, которого Ричард называл «антихристом», и на его место в тот же день был избран Целестин III. На второй день Пасхи, 15 апреля, новый папа короновал короля Генриха и королеву Констанцию императорскими коронами.
Филипп без происшествий совершил переход в Тир, где его приветствовал его родственник Конрад Монферратский. 20 апреля они вместе высадились перед Акрой.
Прибытие Беренгарии пришлось на Великий пост, и поэтому свадьбу пришлось отложить. Получив от Танкреда корабли (принятие подарка, видимо, было отложено до отбытия Филиппа, чтобы тот не мог претендовать на его часть), 10 апреля 1191 г. Ричард вышел в море. Перед этим был разобран «Матегрифон». Дерево было уложено на суда. На одном из кораблей, сопровождаемом двумя галерами эскорта, находились Беренгария и Иоанна. Ричард выстроил флот клином, в вершине которого находился его корабль. Чтобы корабли держались вместе, Ричард приказывал ночами зажигать на верхушке мачты факел. «Этот флот из лучших кораблей и людей он вел, как наседка ведет выводок за кормом, таково было его прирожденное рыцарство», — напишет Амбруаз.