The novel follows two parallel storylines. In the first, Conan is sent to a Brythunian prison mine after he accused his gambling opponent of cheating. Escaping via an underground river, he ends up in a wild region, where he is badly injured in his fight with a bear. He is nursed back to health by Songa, a woman from a local tribe, with whom he eventually settles. Conan finds her tribe's culture and way of life as simplicity rewarding. However, his idyllic life is disrupted when Brythunian soldiers, under orders to locate a magic jewel in possession of the tribe, attack and destroy their village.
The other narrative is the life-story of a sorceress named Tamsin, who, as a child, watched in horror as her mother is raped and killed by mercenaries in the service of Typhas, the king of Brythunia. Tamsin seeks vengeance after she and her doll begin manifesting disturbing magical powers; the doll being possessed by Ninga, a minor deity. Tamsin challenges the kingdom's main cult, in time establishing Ninga's in its place, murders King Typhas, and becomes queen of Brythunia herself. As the fate of Songa's tribe assets, Tamsin's rule proves she is just as corrupt and evil as that of her predecessor.
The two plot threads converge when Conan shows up in Brythunia's capital seeking vengeance. He battles Tamsin, eventually destroying her doll and its powers.