Sometime after leaving Hercules, Xena wanders around on her horse, haunted by the memories of her evil past. Eventually, she comes across a village that's been burned to the ground, the sole survivor of which is a young boy, who asks if Xena has any food to spare. She replies that no one does, then asks him where his parents are. Not realizing who she is, the boy informs her that his parents were killed by Xena, the Warrior Princess. Feeling sorry for him, Xena gives him some food, and rides off. After a while, she stops to bury her armor and weapons in the dirt in an attempt to turn her life around; however, she hears a commotion nearby and goes to investigate. Hiding in the bushes, she finds some villagers being rounded up by a band of thugish warriors. The leader, Hector, demands the women of the village, as he intends to sell them into slavery. When one such woman, Gabrielle, tries to stand up to him, Hector prepares to take a whip to her to teach her a lesson, but is stopped by Xena. Without her armor, he assumes Xena's one of the villagers, only to get soundly beaten by her. Then, realizing that Hector and his men are working for the warlord Draco, she tells him to give Draco a message: "Xena says 'hello'."
Later, as Xena puts her armor back on, Gabrielle eagerly chats with her, awed at how Xena had dispatched with Draco's men. However, Gabrielle's father Herodotus is aware of Xena's reputation, and, not wanting any trouble, requests the warrior woman leave immediately. Understanding, Xena agrees. As Herodotus leaves, Gabrielle asks to accompany Xena, insisting she's not cut out for village life nor does she want to marry Perdicas, the "dull, stupid" fiancé her parents have picked out for her. Unfortunately for Gabrielle, Xena prefers to travel alone, though is helpful enough to reveal that she's heading to a village called Amphipolis. However, Xena warns her not to follow. Meanwhile, Hector returns to Draco's camp, a huge gash in his throat left by Xena. Hector vows to kill Xena the next time he sees her, but Draco warns it'd be foolish to try. That night, Xena catches Draco unaware, and it quickly becomes apparent that the two have a history together. She asks Draco to spare Gabrielle's village as a favor to her, and in return, he asks her to join him by his side. She refuses, informing him that she's going home to Amphipolis. While disappointed, he agrees to do as she's asked, "for old times' sake," though reveals that he'd tried to go home once and his own father nearly beat him with a blacksmith's hammer. He warns that she'll get the same treatment. Back in Gabrielle's village, meanwhile, Gabrille tries to sneak out, but is caught by her sister Lila. Gabrielle insists she's leaving to become a warrior like Xena, maintaining once again that she's "different" and doesn't fit in with the rest of the villagers. Then, after hugging her sister goodbye, Gabrielle leaves. The next day, as Xena and her horse come across a bridge, the horse starts acting crazy, presumably sensing danger.
On the other side of the bridge, they encounter a blind, man-eating Cyclops. Apparently, Xena had been the one to blind him, and he's understandably still upset with her. She suggests he get a new line of work, like hiring himself out to a village as a protector, then rides off, unharmed. Back in Draco's camp, meanwhile, Draco sends Hector and some of his men to follow Xena, with orders to torch Amphipolis and blame it on the Warrior Princess. Meanwhile, back at the Cyclops's bridge, Gabrille is caught by the Cyclops, who intends to eat her. Fortunately, she manages to trick him into letting her go by claiming to be after the "she-demon" Xena. Later, Xena is heading for Amphipolis, when she realizes she's being followed. Using pressure points, she forces Hector into telling her Draco's plan. Gabrielle, meanwhile, is also making her way to Amphipolis. She manages to flag down an old man, and talks him into giving her a ride. In the meantime, Xena arrives in her hometown, heading straight for a tavern run by her mother Cyrene. Upon seeing Xena, however, Cyrene pulls Xena's own sword on her.
Glaring at Xena, Cyrene eventually sets the sword down, informing her daughter that weapons aren't welcome in her tavern and neither is Xena. Despite the not-so-warm welcome, though, Xena tries to warn her mother and the other villagers that Draco is on his way, and offers to help organize a defense. However, Cyrene and the others are still angry about the "last time" Xena talked like that, and tell Xena that they'd rather die than accept Xena's help. Meanwhile, back in Draco's camp, Draco learns that Xena knows of his plan, and so kills Hector for his betrayal. Back in Amphipolis, Xena informs her mother that she came home to make amends for her past, just as an angry mob reveals that Draco's army is on their way, carrying Xena's banner and shouting Xena's name. Believing Draco's army is Xena's and that her daughter hasn't changed after all, Cyrene leaves her daughter to be dealt with by the mob, who begin pelting Xena with stones, even after she unarms herself. However, Gabrielle arrives, and tries to reason with them. She first triest to convince them that Xena's changed, but when that doesn't work, she changes tactics. She argues that, assuming Xena's in league with Draco, Draco's not going to be happy if the mob kills Xena. The villagers relent, but only if Xena and Gabrielle leave immediately. Outside the tavern, Xena starts to leave Gabrielle behind, but then changes her mind once Gabrielle points out that she just saved Xena's life. Later, Xena goes to visit her dead brother Lyceus. She tells him that she'd lost her way after he died, and that she wishes he was there because it's hard to be alone. However, Gabrielle assures Xena that she's not alone.
Back at Cyrene's tavern, Draco and his men find the villagers have already assembled wagons of loot, in the hopes that Draco would take them and move on. However, Draco demands Xena, even preparing to torture a villager when he says he doesn't know where Xena is. Xena returns just then, saving the villager. She then challenges Draco to a fight to the death on some scaffolding, and Draco agrees, ordering his new lieutenant, Gar, to kill whomever touches the ground first. As he and Xena fight, they each try to knock the other off, and wind up having to fight on the heads and shoulders of the villagers. Finally, Draco falls to the ground, and Xena stands on top of him, still not touching the ground. However, she offers him a deal, letting him live in exchange for him and his men getting out of the valley by sundown. Draco takes the deal, then winds up having to kill Gar when his lieutenant tries to kill Xena anyway. As Draco and his army leave, the villagers offer the loot wagons to Xena in gratitude, but she turns and leaves, turning down their offer. That night, as Xena sits around a campfire, she's joined by Gabrielle, and reluctantly agrees to let the younger woman travel with her. The next day, Xena warns that where she's going, there'll be trouble, but Gabrielle is undaunted, pointing out that friends stick by each other no matter what.
