The story begins with Livia, a soft and civilized young woman, as a prisoner of the Bakalah jungle tribe, who have captured her and have killed the brother she was traveling with using excruciating savage tortures. Conan soon appears as the leader of Bamulas, a rival tribe which nonetheless is about to parlay a truce with their rivals. Thinking Conan, being a white man, may feel some kinship with her and assist her, Livia asks him for his help. When Conan balks at her proposal, Livia offers him herself as a sexual reward for rescuing her.
Keeping his side of the bargain, Conan and his warriors slay the Bakalah and their brutal chief after engaging with them in an uncivilized revelry which lasts all night and does much to disgust the proper and civilized girl. Then, when Livia sees Conan drenched in blood coming toward the hut she is kept in, figuring he immediately wants to claim his reward, she breaks their agreement and flees into the thick of the jungle (her clothes ripped off in the process, leaving her naked for the remainder of the adventure) to a strange valley with beautiful blossoms, inhabited by strange brownish-skinned women with apparent lesbian inclinations.
Glad to have found shelter from the blood-soaked "male brutality" of her Cimmerian pursuer, Livia is so enraptured at the eerie beauty of the women and dazed by the hallucinogen scent of the flowers that she barely notice being led to an altar-like section of the glade, where she is to be sacrificed to a bat-like entity. Conan, having pursued her, is soon forced to intervene again on her behalf; after having fought and driven away the demon, Conan jokingly scolds her for having fled, saying he never had the intention to force her into having sex, which in his view would have been as damnable an action as raping her, and that he will soon let her leave the Black Kingdoms since she's too soft to be a proper partner for a Bamula warchief.
The Vale of Lost Tropes:
- Blue Blood: Livia and her brother, of the house of Chelkus, nobles and scientists of Ophir.
- Broken Bird: Livia starts the story in basically complete mental shutdown from the traumas she's experienced.
- Damsel in Distress: Livia, constantly. She needs Conan to rescue her at the start of the story, is distressed by him when he does, and flees into another situation she needs him to save her from.
- Did You Just Punch Out Cthulhu?: Conan sends the bat-winged Eldritch Abomination soaring away for its life with naught but his trusty sword.
- Eldritch Abomination: Livia is almost sacrificed to a large bat-like one before Conan appears and saves her.
- Giving Them the Strip: As Livia madly dashes away from Conan, someone tries to stop her, getting only a handful of her short tunic. Livia rips free if it and him, continuing her flight (and the remainder of the story) stark naked.
- God in Human Form: Well, not human form, but Conan explains that if "Demons from the Outer Dark" want to visit our world, they need to have a body that obeys our world's laws of physics and biology (more or less). Making them susceptible to being stabbed to death by an angry Cimmerian with a sword. Whether or not this actually kills them our just banishes them back to the Outer Dark (and whether that banishment is permanent or not) is left unknown.
- Going Native: Conan has done this with the tribe, although aesthetically it amounts to having adopted a leopard loincloth instead of his regular one and donning a headdress.
- Homoerotic Subtext: The Vale is populated entirely by women and one of them bewitches Livia by kissing her.
- Human Sacrifice: Exactly why is left a bit nebulous, but the Eldritch Abomination of the Vale evidently requests this. The implication is that it protects the Vale's inhabitants... at the cost of their souls.
- Innocent Fanservice Girl: When Livia makes her escape on horseback her clothes are torn off and she spends the rest of the story walking around completely naked. She doesn't seem to mind though, so she's not quite a Reluctant Fanservice Girl.
- Leg Cling: Livia hugs Conan's knees when he promises to send her home.
- Lovecraft Lite: Conan deals with the Eldritch Abomination with a few whacks of a sword. He points out that such beings have to take on a corporeal form to come down to Earth, making them vulnerable.
- No Guy Wants to Be Chased: Conan seems almost embarrassed when he turns down Livia's offer of sex at the end — after all, a civilized woman like her is no companion for a war-chief like him.
- The Promise: Livia promises herself to Conan, bolts in panic, and admits it was wrong after. Conan lets her off.
- Proud Warrior Race: The tribe Conan leads is implied to be this having been "suckled on the teats of war".
- Rewarded as a Traitor Deserves: Pre-emptively! Conan casually decides to stab the chief in the back, because he knows well the other man was planning to do it to him the moment Conan's war-band, the Bamulas, outlived their usefulness.
- Sex for Services: A desperate Livia offers her body if Conan will rescue her, only for Conan to point out that a captive woman doesn't have the option of bargaining for such things.
- The Women Are Safe with Us: Conan tells Livia she's safe with him in the end.