Двадцать третьего сентября во главе флота Ричард торжественно вошел в мессинскую гавань. Флот состоял из 100 кораблей и 14 легких судов. Король шел на первом корабле в окружении ближайших соратников. В изображении очевидца это выглядело так: «Народ теснился на берегу, чтобы увидеть его. И увидели они на горизонте флот из бесчисленных кораблей, который заполнил пролив, и услышали издалека пронзительный звук труб. Когда корабли приблизились, увидели, что они раскрашены разными красками и увешены щитами, блестевшими на солнце. Можно было разглядеть на копьях знамена и вымпелы, которые развевались на ветру. Вокруг кораблей пенилось море, когда они шли, движимые гребцами. Затем под оглушающие звуки труб увидели они того, кого ждали: король Англии стоял в великолепных одеждах на возвышающемся помосте, так, что он мог видеть всех и все могли видеть его». По сравнению с блистательным прибытием Ричарда прибытие Филиппа выглядело довольно жалким. Филипп остановился в одном из дворцов внутри города. Встреча королей, по словам очевидца Ричарда из Дивайзеса, была самой что ни есть дружеской. Армию Ричарда, прибывшую в Мессину 14 сентября, в город не пустили, и она разбила шатры и палатки прямо на берегу. Ричард не захотел останавливаться в Мессине и приказал разбить укрепленный лагерь вне города на холме, поросшем виноградом. У Ричарда были претензии к королю Сицилии Танкреду, и поэтому его торжественное прибытие было еще и демонстрацией силы.
Вильгельм II Добрый, муж сестры Ричарда Иоанны, не оставил прямых наследников и завещал престол своей тетке Констанции, с 1186 года жене принца Генриха, сына Фридриха Барбароссы. Однако к власти в Сицилии при поддержке папы и сицилийских баронов пришел незаконнорожденный племянник Вильгельма Танкред де Лечче и провозгласил себя королем, нарушив клятву верности Констанции. Муж Констанции, будущий император Генрих VI, отправился с войсками добывать наследство жены.
К моменту прибытия на Сицилию Ричарда Иоанна была заперта в замке Палермо. Ричард немедленно потребовал освобождения сестры и выдачи ей вдовьего наследства. Помимо этого Ричард потребовал передать ему наследство, завещанное Вильгельмом Добрым Генриху II, когда тот объявил себя крестоносцем, очевидно, на нужды крестового похода. Наследство это было немалым: несколько полностью оснащенных галер, груженных зерном и вином, шелковая палатка с серебряными кольями на 200 рыцарей, золотые кубки и тарелки, золотые четырехметровый стол и стул.
28 сентября к Ричарду прибыла освобожденная Иоанна. Плененный красотой молодой женщины вдовый Филипп попытался предложить ей через брата руку и сердце. Кроме влюбленности здесь присутствовала и корысть. Отсутствие наследника у Ричарда и его возможная гибель в крестовом походе открывали Филиппу в случае брака богатые перспективы. Ричард вежливо, но твердо отверг идею Филиппа, ссылаясь на предстоящий поход. Стремясь избавиться от своего обручения, он и думать не желал о браке сестры с французским королем.
Иоанна привезла с собой миллион золотых тари (883 кг золота). Сочтя, однако, компенсацию недостаточной, Ричард немедленно переплыл пролив и занял на материке укрепленную крепость - монастырь Баньяра. Там он оставил сильный гарнизон и поселил сестру.
2 октября Ричард изгнал монахов из укрепленного монастыря Сан-Сальваторе на берегу мессинской гавани напротив Баньяры и разместил там выгруженные с кораблей продовольствие и оружие. Захват Ричардом этих стратегически важных пунктов мог быть воспринят Танкредом как угроза войны. Ричард, отправляясь в крестовый поход, как он считал сроком на три года, конечно, не думал начинать с захвата королевства, принадлежавшего хотя и узурпатору, но все же христианскому королю. Тем более что это королевство принадлежало по завещанию не кому-нибудь, а будущему императору. Кроме того, подобную операцию английский король, возможно, уже задумал провести в другом месте. Самое большее, чего хотел Ричард от короля Сицилии, это получить от него как можно больше денег и кораблей для крестового похода.
Но Танкред этого не знал и был готов к самому худшему. И это ему, видимо, усиленно внушал Филипп, ставший его советником и посредником при переговорах. Главной задачей Филиппа было поскорее вернуться во Францию, и, чтобы при этом, лучше всего, Ричард не вернулся. Филипп понимал, что победа в крестовом походе будет победой Ричарда, а поражение означало бы его, Ричарда, почти неизбежную смерть. Поэтому поражение крестового похода было для него предпочтительнее победы.