Gezun of Lorsk becomes embroiled in schemes surrounding a magical gem known as the Potent Peridot, which confers control over the opposite sex. Having been once victimized by the gem, he steals it and plans on returning his prize to a previous owner, the witch-queen Bathyllis of Phaiaxia, who has offered a reward for its return. With his ally, the philosopher Aristax, he undertakes the harrowing journey into Phaiaxia to negotiate with the queen. But nothing is straightforward when dealing with a witch, and there are also other interested parties poised to complicate the situation...

In common with the other Pusadian tales, "The Stone of the Witch Queen" takes place in a prehistoric era during which a magic-based Atlantian civilization supposedly throve in what was then a single continent consisting of Eurasia joined with Africa, and in the islands to the west. It is similar in conception to Robert E. Howard's Hyborian Age, by which it was inspired, but more astutely constructed, utilizing actual Ice Age geography in preference to a wholly invented one. In de Camp's scheme, the legend of this culture that came down to classic Greece as "Atlantis" was a garbled memory that conflated the mighty Tartessian Empire with the island continent of Pusad and the actual Atlantis, a barbaric mountainous region that is today the Atlas mountain range.