Филипп двинулся в Геную, где нанял за 5 850 марок флот для перевозки армии в Святую Землю. Ричард направился вдоль Роны в Марсель, где, как он надеялся, его должен был ждать флот, и прибыл туда 31 июля. Но флот в это время находился еще на пути к Гибралтарскому проливу.

В Марселе Ричарда ожидали паломники. Многие из них уже истратили все, что имели, и просили Ричарда принять их на службу.

Корабли в Бискайском заливе попали в шторм, но благополучно выбрались. Затем в Португалии паломники начали войну с неверными - марокканцами, напавшими на страну, защищали от них Сантарен, самоотверженно сражались с ними на подступах к Лиссабону, помогли в обороне осажденного замка тамплиеров Томар. В это время пронесся слух о смерти марокканского повелителя, и марокканцы разбежались. Главная флотилия численностью в 63 корабля под командой Ричарда Канвилла и тамплиера Робера де Сабле бросила якорь в устье Тахо, ожидая другую из 30 кораблей под командой Гийома де Фор Олерона. Паломники и моряки отправились в Лиссабон, где, полные религиозного рвения, устроили погром мусульманского и еврейского населения, грабили имущество, поджигали дома, убивали и насиловали. Король Португалии Санчо приказал закрыть городские ворота и арестовать пьяных погромщиков. Пока начальство договаривалось с королем об их освобождении, подошла вторая флотилия. Еще через две недели, 24 июля, корабли вышли в море, держа курс на Марсель, прибыли туда 22 августа, но Ричарда там уже не застали.

В Марселе Ричард разделил армию на две части и одну часть под руководством Балдуина, архиепископа Кентерберийского, Ранульфа Глэнвилла и его племянника Хьюберта Уолтера, епископа Солсбери, отправил морем в Палестину. Возможно, это было ответом Ричарда на просьбу о помощи Ги де Лузиньяна, короля Иерусалимского. Нужно отметить, что и до и после этого отряды крестоносцев из разных стран, не дожидаясь королей, на отдельных кораблях и флотилиями прибывали в Святую Землю.

Вместе с другой частью армии Ричард отправился в середине августа на десяти судах и двадцати галерах, нанятых в Марселе, вдоль берега на восток в Геную. В Генуе Филипп слег больным на некоторое время, как писал хронист, из-за последствий морской болезни, и, когда Ричард остановился в Портофино (в 30 километрах), обратился к нему с просьбой отдать ему пять галер из двадцати. Ричард согласился отдать только три. Может быть, почувствовав издевку или не желая выполнять какую-то ответную просьбу Ричарда, Филипп отказался принять дар. Все это не способствовало усилению дружеских чувств между королями. Местом следующей встречи они наметили Мессину.

Медленно, явно не желая прибыть в Мессину, опередив свой флот, шел Ричард под парусами на юг вдоль итальянского берега, часто сходя на берег. В устье Тибра, не заезжая в вечный город, он встретился с кардиналом и епископом Остийским Октавианом и обрушил на него гневное обличение Рима в симонии, очевидно, из-за 1 500 марок, которые он передал папе Клементию III за утверждение Лоншана легатом. Возможно, что Ричард вспомнил расхожую шутку того времени, вошедшую в песни бродячих школяров-вагантов, что самое почитаемое Евангелие в Риме -Евангелие от Марка Серебряного.

В Неаполе Ричард остановился на десять дней. Со свитой поднялся он на Везувий и так близко подошел к огнедышащему кратеру, что окружающим стало страшно. В Салерно он остановился на пять дней. Там он посетил знаменитую медицинскую школу и говорил с врачами. Возможно, темой разговора было его здоровье, возможно, как воин, он интересовался успехами хирургии. В Салерно он получил долгожданное известие: его флот стал на якорь вблизи Мессины. По дороге к Мессине близ Милето захотел он увидеть башню, построенную нормандцем Робером Гискаром, и попал в неприятную историю, которая могла кончиться печально как для него, так и в целом для крестового похода. Проезжая со спутником через маленькую деревеньку, он услышал из одной хижины крик сокола. По понятиям, господствовавшим тогда в Северной Европе, соколом имел право владеть лишь человек благородного происхождения. Ричард вошел в хижину, взял птицу и был атакован толпой разъяренных крестьян, вооруженных камнями и палками. Когда один из крестьян вынул нож, Ричард ударил его плоской стороной меча, который тут же сломался. Отбиваясь камнями, Ричард и его спутник спешно пробились к коням и ускакали.

Двадцать третьего сентября во главе флота Ричард торжественно вошел в мессинскую гавань. Флот состоял из 100 кораблей и 14 легких судов. Король шел на первом корабле в окружении ближайших соратников. В изображении очевидца это выглядело так: «Народ теснился на берегу, чтобы увидеть его. И увидели они на горизонте флот из бесчисленных кораблей, который заполнил пролив, и услышали издалека пронзительный звук труб. Когда корабли приблизились, увидели, что они раскрашены разными красками и увешены щитами, блестевшими на солнце. Можно было разглядеть на копьях знамена и вымпелы, которые развевались на ветру. Вокруг кораблей пенилось море, когда они шли, движимые гребцами. Затем под оглушающие звуки труб увидели они того, кого ждали: король Англии стоял в великолепных одеждах на возвышающемся помосте, так, что он мог видеть всех и все могли видеть его». По сравнению с блистательным прибытием Ричарда прибытие Филиппа выглядело довольно жалким. Филипп остановился в одном из дворцов внутри города. Встреча королей, по словам очевидца Ричарда из Дивайзеса, была самой что ни есть дружеской. Армию Ричарда, прибывшую в Мессину 14 сентября, в город не пустили, и она разбила шатры и палатки прямо на берегу. Ричард не захотел останавливаться в Мессине и приказал разбить укрепленный лагерь вне города на холме, поросшем виноградом. У Ричарда были претензии к королю Сицилии Танкреду, и поэтому его торжественное прибытие было еще и демонстрацией силы.

Вильгельм II Добрый, муж сестры Ричарда Иоанны, не оставил прямых наследников и завещал престол своей тетке Констанции, с 1186 года жене принца Генриха, сына Фридриха Барбароссы. Однако к власти в Сицилии при поддержке папы и сицилийских баронов пришел незаконнорожденный племянник Вильгельма Танкред де Лечче и провозгласил себя королем, нарушив клятву верности Констанции. Муж Констанции, будущий император Генрих VI, отправился с войсками добывать наследство жены.

К моменту прибытия на Сицилию Ричарда Иоанна была заперта в замке Палермо. Ричард немедленно потребовал освобождения сестры и выдачи ей вдовьего наследства. Помимо этого Ричард потребовал передать ему наследство, завещанное Вильгельмом Добрым Генриху II, когда тот объявил себя крестоносцем, очевидно, на нужды крестового похода. Наследство это было немалым: несколько полностью оснащенных галер, груженных зерном и вином, шелковая палатка с серебряными кольями на 200 рыцарей, золотые кубки и тарелки, золотые четырехметровый стол и стул.

28 сентября к Ричарду прибыла освобожденная Иоанна. Плененный красотой молодой женщины вдовый Филипп попытался предложить ей через брата руку и сердце. Кроме влюбленности здесь присутствовала и корысть. Отсутствие наследника у Ричарда и его возможная гибель в крестовом походе открывали Филиппу в случае брака богатые перспективы. Ричард вежливо, но твердо отверг идею Филиппа, ссылаясь на предстоящий поход. Стремясь избавиться от своего обручения, он и думать не желал о браке сестры с французским королем.

Иоанна привезла с собой миллион золотых тари (883 кг золота). Сочтя, однако, компенсацию недостаточной, Ричард немедленно переплыл пролив и занял на материке укрепленную крепость - монастырь Баньяра. Там он оставил сильный гарнизон и поселил сестру.