The film is set during the prehastoric Hybroian Age, a time after the fall of Atlantis but eons before the rise of known ancient civilizations. As a young Cimmerian boy, Conan is instructed by his father on the importance of steel to their people and its relationship with their god, Crom. Soon after, a group of warriors led by Thulsa Doom systematically destroys Conan's village. Thulsa Doom's lieutenant, Thorgrim, whacks the villagers with his hammer, their dogs kill Conan's father and Rexor, another lieutenant of Doom's, steals the sword of Conan's father. Conan's mother is beheaded by Thulsa Doom in front of Conan with the sword Rexor stole. They sell the children into slavery after the village is rampaged.
Having been forced to push The Wheel of Pain (a possibly metaphorical human-powered mill for years, a now-adult and extremely muscular Conan is trained as an arena fighter and then inexplicably freed by his master. He gets chased by wolves and falls into a cave, where he finds a dead king and takes his Atlantean Sword. Conan then meets two thieves: Subotai, a Hyrkanian archer; and Valeria , who becomes his lover. The three break into a fortified temple used by a doomsday cult to steal a large jewel called "The Eye of the Serpent" and Conan discovers that this cult is associated with the warriors who destroyed his village and their leader, Thulsa Doom.
The three become drunk in celebrating their newfound wealth and are arrested by soldiers of King Osric of Ophir . He offers them a fortune to return his daughter, who has been seduced into joining the cult and, he fears, may be charged with assassinating him. Motivated by his hatred for Doom, Conan leaves Subotai and Valeria (who wish to decline the offer) to Set's Mountain of Power.
Arriving at the Mountain of Power, Conan attempts to disguise himself as a priest, but a suspicious guard instead brings him to Thulsa Doom. Conan is beaten by Rexor and Thorgrim, and Thulsa Doom demonstrates the power of flesh by making a young girl jump to her death. Doom orders that Conan be crucified in the desert on the Tree of Woe to contemplate what he has heard. When Valeria and Subotai find him, they take him to a haunted Stonehenge-like cemetery called the Mounds and ask Akiro, the wizard who resides there, to revive Conan. He agrees, but warns that the demons who power the magic involved will "extract a heavy toll"; Valeria declares she will pay them, though Akiro does not explain what that price may be.
With Conan revived, the three enter the Mountain of Power through a gorge that Akiro told Subotai about. They witness, among other things, a cannibalistic feast by its members and Thulsa Doom's transformation into a giant snake. They wreck the harem with brute force and disrupt the cannibalistic orgy. After they grab the princess, Doom shoots Valeria with a poison arrow and she dies in Conan's arms. He cremates her at the Mounds after taking the Eye of the Serpent from her corpse. He then prepares for battle with Thulsa Doom's army.
Thulsa Doom and his lieutenants lead an army of "Vanir" riders to recover Osric's daughter. Conan and Subotai however defeat Thulsa Doom's lieutenants one by one. Thorgrim is defeated by a clever trap and Rexor is defeated by Conan, who is assisted by Crom, in the form of Valeria's spirit. After the battle, Conan recovers his father's sword from Rexor, with its blade broken in the battle. Seeing all is lost in battle, Thulsa Doom attempts to kill the princess. However, Subotai blocks the snake arrow and Thulsa Doom flees. The princess finally returns to her senses.
Thulsa Doom is seen at the Mountain of Power to his followers on the gleam of the eye of Set with their torches. The princess helps Conan infiltrate the mountain. Thulsa Doom attempts to mesmerize Conan. However Conan is too strong willed and using his father's broken sword, beheads Thulsa Doom and tosses the head to the audience and the headless corpse falls down. Conan then drops the broken remnant of his father's sword. The audience throw their torches into the water and Conan throws a torch into the temple, burning it. Conan then brings the princess back home.
The film's epilogue shows an aged Conan sitting upon a throne, crowned as King.