In un'altra avventura sul mare, Xena e Olimpia aiutano Cecrope, il marinaio perduto, che è rimasto bloccato sulla sua nave per secoli a causa di una maledizione afflittagli da Poseidone.Xena (Lucy Lawless) e Olimpia (Renee O'Connor) sono a bordo di un vascello mercantile che si schianta sugli scogli a causa di una tempesta. Xena riesce ad arrivare su un'isola vicina ma Olimpia, travolta dalle acque, viene salvata dalla galea maledetta di Cecrope (Tony Todd), il marinaio perduto. Conoscendo la leggenda della maledizione che dura ormai da trecento anni, Olimpia sente confermate le sue peggiori paure. Cecrope le dice che lei -- e qualsiasi altra persona che salga a bordo -- è destinata a passare il resto della sua vita sul vascello. Chiunque tenterà di scappare, troverà una morte agonizzante nelle acque del mare; cosa che succede ad un marinaio che si trovava assieme ad Olimpia. Quando Xena scopre che Olimpia si trova sulla galea di Cecrope, decide di salvare la sua amica, consapevole del pericolo che corre. Prima però, deve sconfiggere Basculis (Nigel Harbrow), il capo dei pirati che si è rifugiato sull'isola per riparare la nave. Xena fugge ingegnosamente dagli uomini di Basculis, a cui è stato ordinato di catturarla, mentre tiene di vista la galea di Cecrope che naviga lungo la riva.
Nel frattempo, Olimpia sente l'intera storia della maledizione di Cecrope. Il vendicativo dio Nettuno dannò il marinaio a rimanere nel mare per l'eternità a meno che troverà il vero amore, come vendetta per essersi messo contro di lui in una competizione contro Minerva che la fece dea di Atene. Minerva cercò di mitigare la maledizione del dio arrabbiato garantendo a Cecrope l'immortalità, sperando che prima o poi trovi quell'amore. Cecrope dice a Olimpia che l'unica ragione per cui l'ha portata sulla galea maledetta era che stava per essere divorata dagli squali. Quando improvvisamente vede Xena fuggire dagli uomini di Basculis sull'isola e realizza che sta per saltare sulla sua galea, Cecrope ordina ai suoi uomini di salpare il più lontano possibile dalla spiaggia. Xena taglia le corde attaccate alla vela maestra con il chakram, fermando così il vascello. Schivando le frecce che la perseguitano, arriva sulla galea di Cecrope con un salto straordinario. Basculis crede che la Principessa Guerriera stia cercando il tesoro del marinaio perduto e parte all'inseguimento della nave.
Convinta che ci sia un modo per annullare la maledizione, Xena confronta Cecrope, che le confida quanto lo strugge la sensazione di sentire nuovamente la terra sotto i suoi piedi. Quando lo rimprovera per aver smesso di sperare, il marinaio rivela la storia di come Nettuno lo separò dal suo unico vero amore, Tarae, creando un gigantesco gorgo attraverso cui non può navigare. Xena persuade Cecrope a prendere la rotta del villaggio di Tarae, credendo che il gorgo potrebbe essere la chiave per spezzare la maledizione. Continuando il suo viaggio, la galea di Basculis si avvicina a loro e si prepara ad attaccare. Quando entrambi i vascelli stanno per attaccare, il mostruoso Nettuno emerge dalle acque del mare, offrendo a Xena e Olimpia la possibilità di lasciare la nave di Cecrope se non interverrà. Quando Xena rifiuta, Nettuno causa un violento temporale e le casse contenute nella stiva della galea iniziano a sbattere da tutte le parti. Quando una grande cassa sta per schiacciare Cecrope, il suo unico vero amico, Hidsim (George Henare), gli si mette davanti e resta ucciso -- sebbene sappia che Cecrope è immortale. Afflitto dalla morte del suo amico, Cecrope torna nella sua cabina dove viene visitato da Nettuno. Arrabbiato dalla sfida di Xena, il dio offre a Cecrope la libertà se accetta di gettare Xena nel gorgo.
Il temporale se ne va quando Cecrope si dirige verso il gorgo. Una volta che la galea raggiunge il bordo del gorgo di Charybdis, Xena si offre di arrampicarsi sulla guardina per trovare un modo di far passare la nave attraverso le acque agitate. Da quel punto, vede che il vascello di Basculis, che continua a seguire la galea maledetta, viene trascinato nella corrente mortale e infine distrutto. Presto la galea di Cecrope inizia a scricchiolare sotto la pressione del mare. Quando il legno inizia a spezzarsi, Xena si aggroviglia sulla guardina e non riesce a muoversi. Mentre la sua spada cade di sotto, Nettuno appare, chiedendo a Cecrope di dagli la Principessa Guerriera. Invece che darla al furioso dio, Cecrope lancia la spada a Xena, permettendole di liberarsi; poi salta nel gorgo. La nave non sopravvive all'ira di Nettuno ma Xena, Olimpia, Cecrope e il suo equipaggio riescono a salvarsi arrivando sulla vicina spiaggia. La maledizione è spezzata -- non per l'amore che qualcuno da' a Cecrope, ma per il suo amore verso gil altri che ha dimostrato gettandosi nel gorgo per salvare le loro vite.