Xena and Joxer stand on a cliff overlooking the Ionian Sea. Xena's holding onto a blue vase, while Joxer carries with him a scroll. He tries to rip up the scroll, but to no avail. Turns out, it's some kind of binding contract, one which Ares had made and therefore only Ares can destroy it. Instead, Xena says, their best bet is to hide it from him, and apparently, the Ionian Sea is famous for underwater caverns that go on for miles. So, Joxer wraps another scroll around the contract, and gives it to Xena, who then conceals it in the vase and dives for one of the underwater caverns. Fast forward to the present day: two divers emerge from the Ionian Sea, blue vase in hand. Later, at a press conference hosted by C.H.A.K.R.A.M. (Centre for the Historical Accuracy of Key Research in Ancient Mythology), a Dr. Frederick Delaney announces that a new scroll on the life of Xena, Warrior Princess, has been discovered. A couple of fans in the audience get excited, hoping it'll mean a seventh season of Xena, but they're quickly escorted out. Dr. Delaney continues, revealing that the scroll uncovers a new piece of Xena's life, namely that she was married to Ares, god of war.
Dr. Delaney explains that a marriage contract was included with the scroll, and that the scroll itself takes place after Gabrielle had seemingly perished in a lava pit with Hope but before Xena and Gabrielle had reunited. In a flashback, Xena finds Joxer in a tavern, mourning Gabrielle with lots and lots of alcohol, and she cheerfully informs him that Gabrielle is still very much alive. She explains she had a vision, but Joxer just scoffs at that, pointing out that no one could've survived that fall. Nonetheless, he follows Xena out of the tavern. Back in the present, meanwhile, Annie Day, editor-in-chief of Joxer the Mighty Quarterly and the self-proclaimed expert on Joxer, interrupts Dr. Delaney's story, insisting that it was Joxer who initiated the search for Gabrielle and pulled Xena out of the drunken stupor. As she's talking, the two fans from earlier sneak back in, and immediately recognize Annie as the woman who'd learned she was Joxer reincarnated. To Annie's great disappointment, Dr. Delaney informs her that Joxer never once "flexed a heroic muscle". Then, as the conference takes a short break, the two fans approach Annie, and start asking about her past life as Joxer. Annie defends the warrior wannabe, pointing out that he just seems like a fool because the guy who plays him on the show is a goofball. They then ask about Harry and Mattie, Xena and Gabrielle's respective reincarnations, and that's when Annie reveals that the two ended up getting hitched. Excited Xena and Gab finally became a couple, the two head off to tell other Xena fans, leaving Annie to blubber over her recent revelation about Joxer. Meanwhile, back in the past, Joxer and Xena are making their way back to Dahak's temple, even though Joxer still doubts Gabrielle survived, when Xena steps away, claiming to need to use the facilities. Instead, she steps into a wooded clearing, worried that they're not doing so well without Gabrielle but vowing to keep looking for her until she finds her. Just then, Ares appears. He at first taunts Xena over her loss, but then offers to help her find Gabrielle, pointing out that as a god, he can cover a lot more ground than she can. Xena's naturally suspicious, and asks why he's suddenly so willing to help. He says that over the years, he couldn't quite express his true feelings, and then to show what he means, proceeds to take a knee and ask Xena to marry him.
Appalled, Xena kicks Ares in the face, sending him flying back. She says she despises him, reminding him that he's been tormenting her for years. Ares, however, dismisses it as foreplay, insisting he can't get her out of his head or his heart. In an attempt to prove he's sincere, he offers up Gabrielle as a wedding present. Xena takes this as confirmation Gabrielle's alive, but Ares replies that he won't know until he starts looking and that he won't start looking until he has good reason (i.e. Xena's hand in marriage). Xena still doesn't trust him, though, so that's when he offers to marry her in front of the Fates. Later, Xena fills Joxer in on Ares's proposal, explaining that a marriage in front of the Fates is binding and eternal and that Ares couldn't harm her or someone she cares about without harming himself. Joxer asks if she's seriously considering marrying the god of war, to which Xena replies that she's willing to do whatever it takes to get Gabrielle back. That night, Xena is sleeping, when she's awoken by Gabrielle's disembodied voice. The voice tries to tell Xena to stop looking for her, but Xena quickly realizes it's actually Joxer with an improvised megaphone. She calls him an idiot, plopping the megaphone on his head like a duncecap. Back in the present, meanwhile, Harry and Mattie return home from vacationing in Greece, Harry regretting the two goat-cheese milkshakes he had while they were there. Mattie then goes to check the mail, and finds a letter from C.H.A.K.R.A.M., notifying them about the conference and the scroll. Realizing what scroll was found, Harry says that the world could be in a lot of trouble, before he and Mattie speed off towards the conference. Meanwhile, back in the past, Xena summons Ares, informing him that she finally has an answer for him. She beats around the bush for a bit, before reminding him that she'll do anything to get her friend back. With that, she agrees to marry him.
Ares is ecstatic, and promises that Xena won't regret it. Xena, however, has one request: she wants the ceremony to take place at the lava pit in Dahak's temple. Ares thinks it's a bit morbid, but decides to give her what she wants. He then leaves to break the news to Zeus and Hera, pointing out that they'll soon be her in-laws. "Just when you thought it couldn’t get any worse," Xena mutters. Later, after a couple of unsuccessful attempts, Joxer manages to summon Ares to a tavern, where he attempts to throw the god of war a bachelor party. Joxer introduces him to three attractive women, but Ares is less than impressed. So, instead, Joxer brings out the big guns: Xena lookalike Meg popping out of a cake wearing nothing but a whipped-cream-and-cherry bikini. At first, Ares is into the entertainment, but once he finds out she's not Xena (or maybe that she's 'very good friends' with Joxer), he hightails it out of there. Joxer gets to talking with Meg, calling her a classy lady and saying that he's someday going to take her away from "all this". She inquires about Gabrielle, rejoicing when she learns that the blond bard is supposedly dead. Joxer asks her to have a little more respect, but Meg points out that "dead is dead" and nothing can change it. That seems to change Joxer's whole attitude towards tracking down Gabrielle, and he runs off to find Xena. In the meantime, back in the present, Harry and Mattie arrive at the conference, and warn Annie that Ares is very likely to show up and that they're all going to be in danger. Sure enough, Ares is riding down the road on a motorcycle, leaving a trail of withered flowers in his wake. Back in the past, meanwhile, Xena prepares to go through with her and Ares's wedding, white dress and all. Joxer finds Xena and apologizes for being such a downer, before giving her a lock of Gabrielle's hair (something old), a freshly picked flower (something new), and a rabbit's foot (something borrowed). As for the 'something blue,' he says he's it. Then, as he watches, Xena walks down the aisle towards Ares and the three Fates, who are presiding over the ceremony. Ares says 'I do', and then it's Xena's turn. She starts to say it, but then changes her mind and runs off. However, instead of running towards the exit, she heads right for the lava pit, preparing to join Gabrielle.
Joxer watches in horror as Xena falls, blaming Ares for the death of both his best friends. Ares, however, calmly zaps himself out of there, catches Xena as she's falling, and zaps them both back to the wooded clearing. That's when Xena reveals it was all a ploy to expose the fact that he'd used his powers to catch Hope, who was carrying his child, and Gabrielle, who he knew he could use as a bargaining chip. He applauds her detective work, revealing that Gabrielle had made a deal with him after he'd caught her, giving him her soul in exchange for saving Hope. However, he offers to release Gabrielle and her soul, if Xena would be willing to marry him in her next life. As an added bonus, he'll let her and Gabrielle live out the rest of their current lives in peace. Xena is reluctant, but since it's for Gabrielle, she presses her thumb to a contract Ares had drawn up, essentially signing it. As for his part of the bargain, he says he's released Gabrielle, but that Xena will have to find her. He goes to leave, but not before asking Xena what would have happened if he'd really asked for her hand in marriage, no strings attached. Rather than reply, she kisses him passionately, and tells him he'll probably never know. Then, once he's gone, Xena reveals the contract in her hand, apparently having nicked it from Ares during the kiss, and runs off to hide it in the Ionian Sea. Meanwhile, back in the present, Dr. Delaney wraps up the tale, reveling in the fact that C.H.A.K.R.A.M. found the contract before Ares ever could. Just then, as if on cue, Ares bursts into the conference room on his motorcycle. Annie and Mattie realize with horror that all Ares has to do is match the thumbprints on the contract and Xena's soul will be his; Harry, meanwhile, is stuck in the bathroom, those goat-cheese milkshakes disagreeing with him. Annie and Mattie try to stand up to Ares, but there's little they can do. Even Harry, once he finally returns, is powerless is stop Ares from matching his own thumbprint on the contract. As he does just that, Xena and Joxer's souls separate from their respective bodies, and Ares manages to switch them so that Xena's soul resides in Annie's body and Joxer's soul is now within Harry's body. Then, as everyone watches, Xena/Annie proceeds to fight Ares, managing to get the contract away from him. He starts throwing fireballs at her, and she dodges them one right after another, before finally tricking him into destroying the contract with one of those fireballs. She taunts him, reminding him that he made it and therefore only he can destroy it. He insists, however, that she may have won the battle, but he's still going to win the war. With that, he zaps himself out of there, declaring, "Until next time, Xena." Finally, Xena and Gabrielle are reunited, Joxer trailing behind them. Xena compliments Gab/Mattie's hair, then warns Joxer that he may want to stay close to a bathroom.
