Nel tentativo di riavere Xena nella sua armata, Marte escogita un piano coinvolgendo Atrius, il padre di Xena.Xena e Olimpia spiano l'accampamento dell'armata del generale Kirilus (Stephen Lovatt) e vedono molte giovani donne spaventate che vengono rinchiuse in una gabbia dalle guardie. Xena sta per entrare in azione quando un misterioso guerriero, diretto verso il campo, viene avvistato dagli uomini di Kirilus. Urlando per la liberazione delle prigioniere, il guerriero viene attaccato e quasi sopraffatto quando Xena si intromette nel combattimento per salvarlo. Quando Olimpia arriva e chiama Xena, il misterioso straniero le sbalordisce entrambi sostenendo si essere Atrius (Tom Atkins), il padre di Xena. La Principessa Guerriera non ci crede e dice ad Olimpia che suo padre abbandonò la sua famiglia quando ancora era piccola, e se c'è la più piccola possibilità che lui sia veramente Atrius, non vuole avere niente a che fare con lui. Xena e Olimpia vanno al campo per liberare le donne ma Atrius le segue e interviene in un momento critico per assicurare la riuscita dell'impresa. Più tardi, scortando le ragazze a Lotia, Xena ricambia il favore. In un combattimento con spada e lance, la guerriera libera Atrius da due contadini arrabbiati che lo hanno accusato di aver rubato un cavallo.
All'inizio credendolo colpevole, è sollevata di scoprire che l'uomo ha vinto l'animale in una scommessa. Nel frattempo Kirilus, il comandante dell'armata di Marte (Kevin Smith), è infuriato quando il dio della guerra si mostra per dirgli che morirà e verrà rimpiazzato da Xena. Determinato ad uccidere la Principessa Guerriera a tutti i costi, il generale manda l'assassino Tarkus (Lutz Halbhubner) in cerca della donna. Quando Tarkus attacca Xena nel bosco, la guerriera lo mette subito fuori combattimento ma, prima che possa scappare, Atrius lo affronta e lo uccide. Olimpia gli chiede come si fa ad uccidere un uomo che si sta arrendendo e Atrius le risponde che si trattava di difesa personale -- Tarkus aveva un pugnale. Quando Xena sposta il corpo dell'uomo, è sorpresa -- e ancora una volta sollevata -- di trovare un pugnale sotto di lui. Sollecitata da Atrius, Olimpia decide di portare le donne per il resto del viaggio per permettere a Xena e a suo padre di passare un pò di tempo da soli. Quando suggerisce a Xena e Atrius di prendersi cura di Kirilus e di incontrarla più tardi al villaggio, loro accettano. Sulla strada, Atrius prova a conquistare la fiducia di sua figlia e, gradualmente, Xena inizia ad aprirsi.
La loro discussione viene interrotta da una scaramuccia con alcuni soldati di Kirilus. Uno di loro confessa che il resto dell'armata sta circondando Lotia, il villaggio in cui è diretta Olimpia. Atrius insiste di andare a Lotia spiegando piuttosto vagamente che ferì la gente del villaggio tempo prima e che ora vuole il perdono. Nel frattempo Olimpia e le donne arrivano a Lotia e trovano gli abitanti che si preparano ad impedire l'attacco dell'armata di Kirilus. Quando Xena e Atrius arrivano, Atrius viene riconosciuto dal vecchio del villaggio e viene accusato di tradimento. Vogliosa di vendetta, la gente del villaggio lo trascina via malgrado le proteste di Xena. La guerriera li supplica di tenerlo in vita fino a che sarà tornata dopo aver fermato l'armata di Kirilus e se ne va a confrontare il generale. In un combattimento con le spade, Xena colpisce più volte Kirilis e lo sconfigge, dichiarandosi nuovo comandante dell'armata. Tornando a Lotia con la truppa, Xena è scioccata di vedere che la gente ha appeso Atrius tra due pali e lo ha lasciato come cibo per gli avvoltoi.
Nel frattempo, Marte fa infuriare Kirilus quando dice al generale che era solo una pedina nello schema degli dei per far tornare Xena a comandare la sua armata. Con uno sguardo malvagio negli occhi, Xena attacca il villaggio con la sua armata e toglie suo padre dai pali. Mentre Atrius cade a terra morto, Xena ordina alla truppa di uccidere il responsabile della morte di suo padre ma Olimpia interviene e la accusa di essere diventata come le persone contro cui combatte. Quando Atrius apre gli occhi e incita Xena ad uccidere la gente, la Principessa Guerriera si insospettisce. Improvvisamente, Atrius si trasforma in Marte e Xena scopre di essere stata ingannata nuovamente dal dio della guerra. Quando il dio minaccia di ucciderla, la guerriera risponde che preferirebbe morire piuttosto che comandare la sua armata. Marte scompare e Xena e Olimpia continuano i loro viaggi in cerca di nuove avventure.