Салерно был для Ричарда предпоследним этапом перед Мессиной, где уже ждал его Филипп II Август и куда несколько ранее пришел, бросив якорь в отдалении от гавани, его флот, много претерпевший у испанских берегов, но в целом почти не поврежденный. 23 сентября все эти корабли вошли в порт Мессины.
Хронист Ричард Девизский, один из самых точных биографов короля Ричарда, видел в Мессине эту огромную — по тогдашним временам — флотилию. Он насчитывает в ней 100 грузовых судов и 14 легких кораблей, хорошо построенных и хорошо оборудованных, хорошо управляемых, с отлично подготовленными капитанами и матросами. Каждый корабль вмещал сорок боевых коней, столько же рыцарей, множество простых пехотинцев и провиант для людей и коней. Построенные в различных доках Англии, Нормандии и Пуату, эти суда, ходившие и на веслах, и под парусами, отмеченные каждое своим именем (хроникер всякий раз называет название корабля, отличившегося в битве или везшего короля), были лучшими из тех, что способны были создать кораблестроители того времени. Ничего подобного не было в распоряжении Филиппа II Августа. На коротком свидании, которое имели короли в Генуе, он попросил у Ричарда пять галер. Ричард предложил ему три... Филипп отказался от этой подачки и начал переговоры о судах с генуэзцами, затаив не первую уже обиду на своего вассала.
В Мессине его ждали новые уколы. Войдя в гавань со своей свитой на одном корабле (об остальных говорилось, что они «прибудут»), он вызвал всеобщее разочарование населения, высыпавшего навстречу... А когда неделю спустя, 23 сентября, в гавань Мессины вступил флот Ричарда, море зазвучало музыкой военных труб. Сбежавшиеся мессинцы любовались эффектной картиной пестро раскрашенных судов с крыльями драконов по бокам, фантастическими зверями на носу, многоцветными знаменами. «А когда Ричард сел на скакуна и поехал по улицам, видевшие этот кортеж говорили, что это вправду вступление короля, созданного, чтобы править великой землей. Но греки сердились, и лангобарды роптали на того, кто вступал в город с такой помпой...» Обиталище Ричарду было отведено за стенами Мессины, на холме, поросшем виноградом. Едва прибыв на место, он немедленно стал строить настоящий военный лагерь, вокруг которого как символ сурового правосудия расставил виселицы для предполагаемых воров и разбойников. Назначенные им трибуналы с первых же дней открыли свою деятельность, в круг которой попали не только подданные Ричарда, но и беспокоившие их местные жители — прежде всего греки, которых крестоносцы презрительно называли «грифонами».
В Сицилии, где армии предполагали переждать период осенних бурь, обстоятельства не благоприятствовали крестоносцам. В ноябре 1189 года умер последний прямой потомок норманнской династии Гвильельмо Добрый, друг всех крестоносцев, «защитник и покровитель заморских христиан». Претендент на корону, муж его тетки Констанции, император Генрих VI, был далеко. Пользуясь этим, в Сицилии захватил власть представитель боковой норманнской ветви Танкред Лечче. С ним и пришлось сговариваться крестоносцам. Эти переговоры осложнялись намерением Ричарда добиться передачи ему того, что он считал вдовьей частью жены покойного Гвильельмо, королевы Иоанны, которая была его сестрой по матери. Настойчивость Ричарда вызывала у Танкреда (сыграла роль и традиционная дружба норманнских князей с французскими королями) потребность опереться на Филиппа и принять участие в той глухой интриге, сетью которой французский король понемногу опутывал Ричарда. Впрочем, выступать против Ричарда в открытом союзе не было в интересах и не входило в намерения ни Филиппа, ни Танкреда.
В утомительной мессинской эпопее Филипп неоднократно брал на себя — и даже, пожалуй, искренно — роль посредника в тяжбе Ричарда и Танкреда (правда, Амбруаз считает, что его посредничество не было «ни красивым, ни честным»). «Французский король — агнец, английский — лев», — говорили мессинцы еще до того, как им пришлось испытать всю тяжесть «львиных» свойств Плантагенета. Англо-норманнско-анжуйско-аквитанское население лагеря короля Ричарда вело себя вызывающе, под стать своему королю. Обитатели как сельской территории, среди которой расположился этот лагерь, так и самой Мессины, мирно жившие с французами Филиппа, которых было немного и которые вели себя осторожно, подражая своему королю, с глубоким отвращением относились к забиякам армии Ричарда. Множество мелких недоразумений, столкновений, злых выходок, а то и преступлений лукавых «грифонов» («они, чтобы нас обидеть, закрывали пальцами глаза, они называли нас смердящими псами, а также обезьяньими хвостами, каждый день чинили пакости, убивали наших паломников и кидали их тела в отхожие места»), встречные грубости и насилие со стороны непрошеных гостей — все это непрерывно питало взаимное раздражение.