"The Frost-Giant's Daughter" is the earliest chronological story by Robert E. Howard in terms of Conan's life. The brief tale is set somewhere in frozen Nordheim, geographically situated north of Conan's homeland, Cimmeria. Conan is depicted by Howard as an young mercenary, traveling among with the golden-haired Aesir in a war party. Shortly before the story begins, a hand-to-hand battle has occurred on an icy plain. Eighty men ("four score") have perished in bloody combat, and Conan alone survives the battlefield where Wulfhere's Aesir "reavers" faced the Vanir "wolves" of Bragi, a Vanir chieftain. Thus, the story opens.
Following his fierce battle against the red-haired Vanir, Conan, lying exhausted on a corpse-ridden battlefield, is visited by a beautiful and partially-nude woman identifying herself as "Atali". Upon her bodice, she wears a transparent veil: a wisp of gossamer that wasn't spun by human origin. The mere sight of her strange beauty awakens Conan's lust and, when she repeatedly taunts him, he insanely chases Atali for miles across the snow-covered region while attempting to capture her.
Mocking him with each step, Atali lures Conan into an ambush. Undaunted by the snare, Conan slays her hulking twin brothers, two Frost Giants, and captures Atali in his arms. However, Atali calls upon her father, Ymir, to save her. Before Conan is able to ravish her, Atali disappears in a stroke of lightning which seemingly transforms the landscape and renders him unconscious.
Later, when his Aesir comrades arrive, Conan believes he simply dreamed the bizarre encounter. Suddenly, Conan realizes he's still gripping onto a translucent veil which served as the sole garment of the Frost-Giant's daughter.
The utilization of poetic descriptions throughout this tale is quite strong, and on par with Howard's "Queen of the Black Coast". However, the narrative is often criticized by Howard scholars for not having the more detailed plotting of his superior Conan stories such as "The Black Stranger". Largely, this is because Howard was aiming for a mythological feel, something to which the story is eminently suited.
This is the only Conan story in which other characters refer to him as "a southerner". In all the rest of his wanderings, Conan is invariably "a barbarian from the cold north", but for the Aesir and Vanir, Cimmeria is a southern land, a bit less cold than theirs.