Alla nascita e all'affermazione della leggenda di Riccardo Cuor di Leone Messina diede un contributo decisivo. Fu in riva allo Stretto, infatti, che il sovrano inglese venne soprannominato per la prima volta il Leone, per distinguerlo dal re di Francia, Filippo Augusto, che venne chiamato l'Agnello. Riccardo, infatti, a differenza di quest'ultimo, si era dimostrato molto deciso nel riportare l'ordine in città subito dopo il suo trionfale arrivo a Messina, la domenica del 23 settembre del 1190, punendo con durezza e rapidità quanti tra i suoi, ma anche tra la popolazione, avevano dato vita a disordini e si erano addirittura macchiati di stupri e saccheggi. Era accaduto che i suoi uomini appena messo piede a Messina avevano preso a insidiare le donne siciliane e a razziare tutto quello che potevano, provocando la reazione di una parte della popolazione, i Grifoni.
I Grifoni erano quella parte di popolazione di origine greca che a Messina deteneva le leve del potere politico ed economico, vessando la «parzialità latina». I crociati vennero in urto con i Grifoni, che avevano mal digerito il loro spocchioso arrivo in città e perché li consideravano i discendenti di quegli altri Normanni che, un secolo prima, agli ordini di Roberto il Guiscardo e di suo fratello Ruggero, avevano conquistato la loro isola.
Ma perché Riccardo Cuor di Leone e Filippo Augusto si trovavano a Messina in quello scorcio del 1190 ? I due sovrani erano diretti in Terra Santa per partecipare con Federico I Barbarossa alla Terza Crociata, che aveva lo scopo di riconquistare alla Cristianità Gerusalemme, in mano al Saladino. Messina costituiva un punto di passaggio obbligato verso il Medio Oriente. Le flotte dei due sovrani partite da Marsiglia e Genova dovevano incontrarsi a Messina e quindi ripartire per la meta finale. Il re di Francia giunse in Sicilia il 16 settembre e venne ospitato da Tancredi, che aveva preso il potere dopo la morte di Guglielmo il Buono, a Palazzo Reale, mentre i suoi guerrieri avevano trovato ospitalità al centro della città. Riccardo, invece, venne alloggiato nella casa di un certo Regnaud de Mousquet (o forse de Moac), che si trovava fuori le mura, tra i vigneti. Si preferì non fare mischiare i due eserciti, tenuto conto che comunque i rapporti tra i due sovrani proprio buoni non erano.
Filippo, quello stesso giorno, decise di fare vela verso la Terrasanta, ma il vento contrario l’aveva dissuaso. Riccardo, invece, prima di ripartire voleva risolvere la questione della dote della sorella. Giovanna, infatti, aveva sposato il re di Sicilia Guglielmo il Buono, alla cui morte, non avendo egli figli, si scatenò una lotta senza quartiere per la sua successione, che vide contrapporsi un cugino bastardo di Guglielmo, Tancredi da Lecce - figlio illegittimo del duca Ruggero di Sicilia - e Costanza, sua zia, moglie di Enrico di Hohenstaufen, che sarebbe diventato imperatore con il nome di Enrico VI. La spuntò Tancredi, che confinò Giovanna a Palermo, trattandola da ostaggio, perché non aveva nessuna intenzione di restituirle la dote.
Ma il trionfale e minaccioso ingresso di Riccardo a Messina, lo riportarono a più miti consigli, tanto che Giovanna tornò a Messina, dove arrivò il 28 settembre, in tempo per diventare un ulteriore motivo di contrasto tra il fratello e il re di Francia, il quale appena la vide se ne innamorò. Ma Riccardo era contrario a questo legame e condusse la sorella a Bagnara. Quindi il 2 ottobre occupò il monastero di San Salvatore. Il colpo di mano non piacque ai greci, cioè ai grifoni, che in questo videro il tentativo di Riccardo di voler conquistare la Sicilia. Scoppiarono scontri tra gli uomini del re e gli abitanti della città, che chiusero fuori le mura i crociati. Riccardo sedò la rivolta e saccheggiò Messina. La cosa non piacque per nulla a Filippo. Riccardo allora, come gesto di buona volontà, consegnò la città in mani neutrali, cioè ai cavalieri Templari e agli Ospitalieri. Ma per non smentirsi, fece costruire in cima alla Rocca Guelfonia un castello che volle chiamare Matagrifon, cioè "ammazza greci”.
Intanto, Riccardo e Tancredi trovarono l’accordo sulla dote di Giovanna, a condizione che Riccardo appoggiasse Tancredi contro l'imperatore Enrico VI, che pretendeva che la corona della Puglia e della Sicilia passasse alla moglie Costanza.
Le condizioni climatiche, intanto, non permettevano alle due flotte di salpare e questo non faceva che crea problemi tra soldati e cittadini, che spesso venivano alle mani.
L'inverno a Messina passava lentamente e per cercare di vivacizzare la permanenza si organizzavano feste, giochi e giostre. In occasione di una di queste, il 2 febbraio, festa della Purificazione di Maria Vergine, le tensioni tra Riccardo e Filippo Augusto esplosero. Accadde che mentre i due gruppi si dirigevano fuori città, incrociarono un contadino il cui asino trasportava un carico di giunchi. Sia Riccardo che i suoi uomini, così come i francesi si impadronirono dei legni e improvvisarono una disfida sul posto. Riccardo affrontò un fedelissimo del sovrano d'Oltralpe, Guglielmo di Barres. Nello scontro Riccardo però ebbe la peggio, un colpo dell'avversario gli lacerò la sopravveste. Il re s'infuriò e cercò di disarcionarlo senza riuscirci. Calmato dai suoi Riccardo pretese da Augusto che l’avversario venisse allontanato. Trascorsi pochi giorni da quell'episodio, Riccardo in un impeto di generosità che faceva il paio con le violenze dei Plantageniti, fece regalo dei suoi beni alla truppa e donò parecchie navi al re di Francia.
Ma prima che la flotta lasciasse la Sicilia per far vela verso la Terra Santa, la tensione tra inglesi e francesi risalì. Riccardo si recò a Catania per incontrare Tancredi, in compagnia del quale trascorse cinque giorni – dal 3 all'8 marzo 1191 – tra feste e gesti di reciproca distensione. Tancredi donò a Riccardo 4 grosse navi e 15 galee, da parte sua il sovrano inglese gli regalò la mitica spada di re Artù, Excalibur, ritrovata nell'abbazia di Glastonbury.
Durante il viaggio di ritorno a Messina, Tancredi confidò a Riccardo che il re di Francia stava tramando alle sue spalle. E per avvalorare quanto sosteneva gli mostrò le lettere di Filippo Augusto. Il re inglese arrabbiato affrontò il sovrano francese, che imbarazzato gli ribattè che quelle missive erano un falso e che Riccardo così facendo cercava pretesti contro di lui allo scopo di non rispettare l'impegno di sposare sua sorella Alice. «Non respingo la sorella del re di Francia – rispose Riccardo -, ma mi rifiuto di sposarla perché è noto che lei era l'amante di mia padre, da cui ebbe un figlio». Filippo Augusto sciolse dall'impegno Riccardo, che così poteva sposare, come voleva sua madre Eleonora, Berengaria di Navarra.
Giunta la primavera e migliorate nettamente le condizioni atmosferiche le flotte si apprestavano a fare vela per il Medio Oriente. Il primo a lasciare Messina, il 30 marzo, fu Filippo Augusto. Riccardo lo seguì con qualche giorno di ritardo. Sulla data della partenza c'è divergenza tra gli storici: c'è chi sostiene che avvenne il 10 aprile del 1191, altri il 14. Gli storici concordano nel dire che prima di andare via Riccardo fece smontare e caricare sulle navi il castello di Matagrifon, che venne rimontato e utilizzato nell'assedio di Acri.