A decade and a half after the events of Conan the Conqueror, King Conan of Aquilonia is hunting with Prince Conn, his teenaged son and heir. The boy is captured by a band of Hyperborean witch-men, servants of the witch queen Louhi, as bait to lure Conan into a trap.
Conan travels north to Hyperborea for the first time since escaping captivity there during his own youth in "The Thing in the Crypt". To reach the citadel of Pohiola, where the prince is being held, Conan fights his way through desolate country, battling flesh-eating swamp people and braving near-starvation. He crosses the Hyperborean border, marked with a gigantic, rune-inscribed skull and ultimately enters the citadel.
Confronting Louhi, he is able to free his son, discovering in the process that his arch-enemy, the Stygian sorcerer Thoth-Amon, is behind the plot.