Herc, Xena, and Salmoneus make their way to Elysia via hilly terrain. They stop for a bite to eat, with Salmoneus assigned the task of catching some quail for lunch and Herc the task of cooking it, leaving Xena to go scout ahead. As Salmoneus attempts to locate some quail, he's tackled by Iolaus, who doesn't believe Salmoneus's claim that he's Herc's best friend. So, Salmoneus takes him to meet Hercules, not knowing that Herc and Iolaus are already acquainted. Herc even pretends not to know Iolaus, before dropping the act and greeting his friend. He asks what brings Iolaus to these parts, to which Iolaus replies that he heard that Xena is on the loose. Rather than explain that Xena is now good, Herc gets evasive and instead tells Iolaus that the real problem is Darphus. Meanwhile, Xena comes upon a group of soldiers looting a village. She attacks, but one of the soldiers, Quintas, gets away. She yells after him, "Tell Darphus I'm coming for him!" That night, Quintas relays Xena's message, and even though Darphus is glad to hear it, he feeds Quintas to Graegus for abandoning his comrades while they fought Xena. Meanwhile, Herc, Iolaus, and Salmoneus are sitting around a campfire, enjoying roasted quail. Herc is about to tell Iolaus about Xena, when the warrior princess joins them. Iolaus immediately goes on the defense, but Herc assures him that he and Xena are on the same side. Iolaus assumes Herc is falling into the same trap he fell into, and tries to leave, refusing to watch history repeat itself. Herc stops him, though, insisting that Xena has changed. He fills in his friend about Xena saving the baby in Parthis, but Iolaus remains skeptical. However, he is willing to stay and help them with Darphus. The next day, Herc and company are back on the road, Iolaus intentionally trailing far behind. They reach a canyon, and Herc stops, pointing out that it's a good spot for an ambush so everyone should stick together and be on alert. They proceed, only to get trapped by some falling rocks, thanks to Darphus up top.
Thankfully, Herc managed to catch the biggest rock, and holds it up on his back while Xena and Iolaus try to dig their way out, with Salmoneus sitting frozen in fear. Meanwhile, Darphus and his army celebrate the death of Hercules. They hear Graegus growling, and Darphus raises a toast to the dog of war, saying that they will soon join Graegus in helping Ares fulfill his destiny of ruling the world. Back down in the canyon, Xena and Iolaus manage to dig their way out, while Salmoneus still sits paralyzed with fear. Propping up the rock he was holding, Herc gets himself and Salmoneus out of there before the whole thing caves in. Out in the fresh air, Salmoneus expresses shame for his reaction, believing himself to be a coward. Herc reminds Salmoneus how he'd helped him take on some centaurs when he'd lost his eyesight, but Salmoneus will hear none of it and wanders off. Turning her attention to Iolaus, Xena offers to bandage a head wound he'd sustained, but he refuses her help and wanders off as well. That night, Herc, Xena, and Iolaus sit around a campfire, with Salmoneus asleep nearby. Iolaus excuses himself to go check the perimeter, leaving Herc and Xena alone. Xena worries about Iolaus and his hatred of her, but Herc assures her that when the time comes, Iolaus will put his resentment aside to fight Darphus. Xena then asks Herc if he too will go back to hating her when this is all over, pointing out that she's done so many terrible things. Herc argues that she's off to a good start towards redemption, what with saving that baby in Parthis. Xena counters that when Herc helps people, he does it to honor his wife and children, whereas Xena has no such motivation. Herc, however, disagrees, saying that Xena has the goodness in her heart. The next day, Darphus and his army prepare to pillage a diamond mine, planning to use the diamonds to pay tribute to Ares and the miners to feed Graegus. Afterwards, he says, Graegus will be at full size, ready to fulfill Ares's will. Meanwhile, Herc and company are trying to evacuate the diamond mine ahead of Darphus's attack, but the miners refuse to leave. Just then, Darphus and his men arrive. Rather than flee, though, the miners actually help Herc and company fend off the raid. At one point, Iolaus is outnumbered, but Xena intervenes, saving him. Then, seeing Darphus, Xena tosses a sword at Darphus's chest, but to no effect. However, as Darphus sees his men getting soundly defeated, he quickly calls for a retreat. As Herc and Xena watch Darphus leave, Iolaus comes to inform them that everyone's fine, but that Salmoneus is missing.
Later, Iolaus has a talk with Xena. He asks her why she saved him, and she responds that they're on the same side. He reminds her that it wasn't that long ago that she tried to kill him to get to Herc, to which she expresses regret. She says she was twisted up by hate, and figures that that's the same feeling Iolaus has towards her. Iolaus replies that he doesn't hate her anymore, and the two shake hands. Just then, Herc returns from searching for Salmoneus, glad to see Xena and Iolaus getting along. Unfortunately, all Herc found was a manuscript Salmoneus had been working on, which Herc hesitates to share with them. However, he does divulge that he found some footprints that might belong to Salmoneus, leading to Elysia. Meanwhile, Darphus chastises his men for running from Herc and Xena. One of the men points out that he fled too, only to get stabbed and fed to Graegus for his trouble. Darphus insists that he doesn't flee, he only lives to fight another day. He then tells the rest of his men to prepare for Herc and Xena's arrival, warning that if they fail, they too will be fed to Graegus. In the meantime, Herc, Xena, and Iolaus find wagon tracks that head towards the ocean and then veer towards Elysia. Turns out, Salmoneus had hitched a ride with a merchant with poor eyesight. The merchant takes him to Elysia, mistaking it for a fishing village, and the two are captured by Darphus's men. Meanwhile, Herc and Xena work on setting up camp, while Iolaus scouts ahead. Xena says that before a battle, she used to feel nothing but cold rage, but now she's starting to understand what it's like to be Hercules, feeling good about challenging the forces of evil. She says she wouldn't be doing it if not for him, but he counters that she made the decision all on her own. She replies that she's come to another decision: to tell Herc how she feels about him, in case she dies fighting Darphus. The two then kiss passionately. Back at Darphus's camp, meanwhile, Iolaus spots Salmoneus being plied with food and wine, presumably being fattened up for Graegus, and gets the wrong idea. Just then, he hears Graegus roaring, and runs back to tell Herc and Xena. However, Herc and Xena are in the middle of making love.
Iolaus returns in the aftermath of Herc and Xena's lovemaking, and is amused when they act caught. On a more serious note, though, he reports his findings, insinuating that Salmoneus is a traitor. Herc, however, finds it hard to believe that Salmoneus would betray them for Darphus, but Iolaus points out that they have a bigger problem to worry about: Graegus. Fortunately, Herc has a plan: fight evil with evil. Later, Herc and company knock out a couple of Darphus's men, commandeering the merchant's wagon, just as Darphus prepares to sacrifice Salmoneus to Graegus. Iolaus tries and fails to set the wagon on fire, before giving up and sending it rolling down the hill to Darphus's camp, with Iolaus on top of it. He starts fighting Darphus's men, with Herc and Xena quickly joining the fray. Herc makes his way down to Graegus's lair, where Salmoneus has been chained up, while Xena confronts Darphus himself. As Herc tries to fight off the dog of war, Xena and Darphus's fight takes them down into Graegus's lair, where Xena uses her sword to free Salmoneus. Outside, Salmoneus sees Iolaus fighting Darphus's men, and jumps in to help, grabbing a small cooking pan and knocking Darphus's men unconscious. Herc, meanwhile, manages to chain Graegus to a post, but the chain doesn't hold for long. As the chain snaps, Xena and Herc manage to put Darphus right in Graegus's path, causing Darphus to be eaten and Graegus to be vanquished. Later, Herc returns Salmoneus's manuscript to him. Having had his confidence restored, he tells Herc and Iolaus goodbye, and sets off for Athens to work on Herc's biography. Then, Iolaus says he's heading home, and asks if Herc wants to come along. Herc, however, responds that there's someone he needs to talk to first. He finds Xena preparing her horse to leave, and the two share another passionate kiss as Herc tries to convince her to stay with him. She insists that she has so much to atone for, and that she needs to get started making amends. Herc wishes she'd let him help, and she replies that he already has, by unchaining her heart. After giving Herc one last kiss, Xena says goodbye, and rides off. Iolaus then approaches, asking if Herc is alright. Herc replies that he is, and that at least the good guys won.
