Король Филипп Август был совершенно иным человеком. Он был на восемь лет младше Ричарда, но царствовал уже более десяти лет, и нелегкий опыт сделал его мудрым. Наружностью он был не ровня Ричарду. Филипп был хорошо сложен и густоволос, но слеп на один глаз. Личной смелостью он не отличался. Несмотря на себялюбие и холерический темперамент, он умел скрывать свои страсти. Он не любил показухи — ни эмоциональной, ни материальной.
Двор его был скучен и строг. Филиппа не волновало искусство, да и глубокой образованностью он не отличался, хотя осознавал пользу ученых людей и стремился заручиться их дружбой из политических соображений, а удерживал ее благодаря остроумию и умению поддерживать содержательную беседу. Как политик он был терпелив и наблюдателен, хитер, вероломен и беспринципен. Но при этом его отличало сильнейшее чувство долга и ответственности. Несмотря на всю мелочность по отношению к себе самому и своим друзьям, он был щедр к беднякам и защищал их от угнетателей. Это был малопривлекательный и малосимпатичный человек, но хороший король. Среди франков Востока он пользовался особым авторитетом, ибо он был сюзереном аристократических родов, из которых они в большинстве своем и происходили; и большинство прибывающих на Восток крестоносцев прямо или косвенно принадлежали к числу его вассалов. Но им больше был по сердцу Ричард с его отвагой, рыцарской удалью и обаянием; а сарацинам Ричард казался более благородным, богатым и великим из двух монархов.
Короли вместе двинулись в путь из Везле 4 июля 1190 года. Ричард послал английский флот вперед, который должен был обогнуть Испанию и встретиться с ним в Марселе, но почти все сухопутные войска, набранные в его владениях, были вместе с ним. Армия Филиппа была не столь многочисленна, так как многие из его вассалов уже отправились на Восток. Французская армия, по пятам за которой следовала английская, выступила из Везле в Лион. Там, после того как французы перешли через Рону, мост рухнул под тяжестью английских полчищ. Многие погибли, и произошла небольшая задержка, пока смогли организовать транспорт. Вскоре после ухода из Лиона пути королей разошлись. Филипп двинулся на юго-восток через предгорья Альп, чтобы выйти к побережью у Ниццы и затем направиться вдоль моря к Генуе, где его ждали корабли. Целью Ричарда был Марсель, где 22 августа к нему присоединился английский флот. Его плавание было ничем не примечательным, не считая того, что в июне моряки ненадолго задержались в Португалии, где помогали королю Саншу отразить вторжение императора Марокко. Из Марселя часть соратников Ричарда под началом Балдуина Кентерберийского прямиком отправились в Палестину по морю, но основная армия на нескольких караванах судов отправилась в сицилийскую Мессину, где предполагалось снова соединиться с французами.
По предложению короля Сицилии Вильгельма II Ричард и Филипп, еще планируя совместный поход, решили собрать свои силы у него на острове. Однако в ноябре 1189 года король Вильгельм умер. Он был женат на сестре Ричарда Иоанне, но брак их был бездетным, и наследником стала его тетя Констанция, жена Генриха Гогенштауфена, старшего сына Фридриха Барбароссы. Многим сицилийцам мысль о правителе-немце была ненавистна. Благодаря небольшой интриге при поддержке папы Климента III, которого тревожили перспективы того, что Гогенштауфены возьмут под контроль Южную Италию, на трон вместо Констанции и Генриха уселся незаконнорожденный кузен покойного короля — Танкред, граф Лечче. Танкред, некрасивый, низкорослый и ничем не примечательный человечек, почти сразу же оказался в гуще многочисленных проблем. На Сицилии подняли мятеж мусульмане, а германцы вторглись в его земли на материке; и избравшие его вассалы уже начали жалеть о своем выборе. Танкреду пришлось отозвать своих людей и корабли из Палестины, и с их помощью он разделался со своими врагами. Но хотя он был готов со всеми почестями принять королей-крестоносцев и снабдить их продовольствием, он не имел возможности сопровождать их в крестовый поход.