Quando la malvagia amazzone Velsinea riceve l'immortalità mangiando dell'ambrosia, Xena escogita un piano per sconfiggerla mettendola contro Callisto, nel frattempo diventata immortale.Mentre Xena e Olimpia si preparano a lasciare il villaggio amazzone, Olimpia consegna la maschera della regina ad Anfitea (Danielle Cormack) di fronte alle amazzoni. La gioiosa occasione viene subito interrotta da Velsinea (Melinda Clarke), che arriva tra la folla trascinandosi una gamba con il corpo sanguinante. Tutte sono stupite del suo ritorno, credendo che sia morta durante la battaglia nella sala dell'ambrosia. Furiosa con Olimpia per averle "rubato" la sua regalità, prende in mano un piccolo frammento di ambrosia che, dopo il precedente combattimento, era caduto vicino a lei. Velsinea la ingerisce e viene immediatamente trasformata in una dea. I suoi occhi diventano bianchi e le sue ferite guariscono miracolosamente. L'amazzone lancia una sfera di energia contro Olimpia, che viene portata in salvo da Xena prima che venga colpita. La difesa delle amazzoni sembra essere inutile. Velsinea continua a lanciare sfere di energia che colpiscono le spade delle amazzoni, facendole cadere dalle loro mani. Realizzando di essere il bersaglio principale, Olimpia fugge nel bosco, dove si riunisce a Xena e Anfitea, che ha ordinato alle amazzoni di ritirarsi.
Le amazzoni si rifugiano in una caverna per raggrupparsi e curare le loro ferite. Sapendo che solo un immortale può combattere con un altro immortale, Xena pensa di mettere Callisto (Hudson Leick) -- diventata immortale in "Hercules e la sorpresa di Callisto" -- contro Velsinea. Anfitea e le sue amazzoni creano una diversione per dare tempo per scappare a Xena e Olimpia ma Velsinea le fa fuggire nuovamente. Il giorno seguente, Xena e Olimpia giungono all'entrata del labirinto degli dei, in cui la malvagia Callisto, con una cicatrice causatale da Hercules, è stata rinchiusa per l'eternità. Xena offre a Callisto l'opportunità di ingerire l'ambrosia in cambio di aiuto e lei accetta. Mentre le due escono dal labirinto sotterraneo, Olimpia è costretta a confrontare l'odiata Callisto, che ha ucciso il suo amato marito. Prima che Callisto cooperi con Xena, forza la Principessa Guerriera a fare una pubblica confessione in cui racconta di aver distrutto Cirra, il villaggio di Callisto, anni prima. In una sfuriata, Velsinea distrugge il tempio di Diana, la dea delle amazzoni, mentre Xena porta Olimpia e Callisto in un canyon senza uscita dove progetta di lanciare le due immortali in battaglia. Quando Velsinea entra nel canyon, pienamente consapevole della presenza delle tre donne nascoste, Callisto salta fuori dal suo nascondiglio lanciando il chakram di Xena contro alcune pietre.
Xena realizza di essere stata ingannata quando Callisto urla a Velsinea che loro condividono lo stesso scopo -- il loro odio per Xena e Olimpia. Determinata a spezzare la potente alleanza tra le due, Xena salta fuori dal suo nascondiglio, urlando a Callisto di iniziare l'attacco. Quando Callisto protesta, Velsinea inizia a lanciare sfere d'energia verso Xena e Olimpia. Sapendo che Velsinea sta ancora imparando ad usare i suoi poteri e che continua ad avere dei momenti di stanchezza, le due corrono intorno cercando di stancarla. Quando Callisto spinge Velsinea per attirare la sua attenzione, Velsinea la manda in volo contro una roccia con una potente sfera d'energia. Con i suoi poteri temporaneamente esauriti, Velsinea viene attaccata da Xena, che la spinge contro una roccia con la sua spada. Nel momento in cui i poteri di Velsinea tornano, Callisto ha il suo sguardo assassino. Infuriata dal tentativo di Velsinea di ucciderla, Callisto si unisce a Xena contro l'amazzone.
Le due corrono sotto una sporgenza e, usando il chakram, causano una frana che la investe. Realizzando di averla fermata per un po' di tempo, Xena nota un altro canyon con delle vecchie rovine e un torrente di lava, dove pensa di buttarci Velsinea. Quando l'amazzone riesce a liberarsi, si trasforma in un turbine di polvere, distruggendo tutto quello che si trova davanti in cerca delle sue nemiche. Poco dopo raggiunge le rovine ma Xena riesce a salvare Olimpia prima che venga risucchiata nel mini tornado. Quando Velsinea inizia a lanciare sfere infuocate giganti, le tre donne fuggono sull'orlo del baratro in cui scorre il fiume di lava. Prima che Velsinea possa uccidere Olimpia, Callisto l'attacca, chiedendole l'ambrosia. Nel combattimento che segue, Velsinea fa cadere l'ambrosia, che Olimpia afferra e lancia a Callisto. Callisto la ingerisce e si trasforma immediatamente in una dea. Mentre le due immortali iniziano una furiosa battaglia sul ponte di corde sospeso sopra il fiume di lava, Xena spezza le corde con il chakram, facendole cadere entrambe nella lava, sicura di non sentirle più per molto tempo.