"Red Nails" begins in the jungles far to the south of any known civilized or barbarian lands, where Valeria of the Red Brotherhood and Conan (her would-be lover) are set upon by a "dragon" (actually a dinosaur, though described with the characteristics of a stegosaurus and an allosaur) that mauls their horses. The pair retreat to a crag the monster cannot scale, but has no food or water. Conan recognizes some poisonous fruit growing nearby; they coat the tip of a spear with its juice, and pierce the jaws of the monster with it. Although blinded, the raging monster pursues them by their scent. Overtaken, Conan whirls to face the beast and lures it to its death.
Conan and Valeria emerge from the jungle to make their way to a walled city they spotted from the crag. Finding no grazing herds or cultivated fields around the city, they assume it is deserted. They force the rusted gates and enter a bizarre twilight world: the city is a single massive structure made of jade with traces of other materials, consists entirely of four tiers of rooms, chambers and passageways. A single great hallway runs the length of the city, but there are no other streets or open courtyards. The pair separate to search the city. Valeria encounters a man named Techotl whom she saves from his would-be killer; Conan arrives in time to save them from his comrades. Techotl invites Conan and Valeria into the stronghold of his people, the Tecuhltli, where they welcomed by the rulers, Olmec and Tascela.
In the stronghold Conan and Valeria learn that the city of Xuchotil was built long before its current inhabitants arrived. The people who created the city had used magic to resurrect "dragons" (actually the jumbled skeletons of dinosaurs) to protect the city. One day, a slave named Tolkemec betrayed his masters to guide a band led by the brothers Tecuhltli and Xotalanc into the city which slaughtered the original inhabitants. The conquerors afterwards ruled the city in peace until Tecuhltli stole the bride of his brother, leading to a feud in which most of the conquerors are killed. Tolkemec played both sides for his own purposes before he was exiled to the catacombs and assumed to have died there. Nails driven into pillar in their stronghold keeps count of how many of their enemy they have slain, and provides the title of the story.
The arrival of Conan and Valeria precipitates the final showdown in the decades-long feud. Members of the Xotalanc clan manage to break into the Tecuhltli stronghold, but they are outnumbered. With the help of the formidable fighters Conan and Valeria, the Tecuhltli win the grim battle, and the Xotalanc are all killed. Olmec is exultant at this final victory, though sorry that none of his enemies was taken alive to be slowly tortured to death - as both sides to the conflict regularly did to prisoners. However, his gratitude to his two allies is definitely short-lived.
Having no intention of letting Conan and Valeria leave the city, Olmec secretly orders his men to kill Conan. While Olmec attempts to force himself on Valeria, he is thwarted by Tascela who imprisons him. She is revealed to be a sorceress and bride whose kidnapping started the feud. Tascela plans to use Valeria's vitality to restore her youth. After killing off his assassins, Conan returns to Tecuhltli, reluctantly frees Olmec, only to kill him when Olmec proves untrustworthy. Conan finds the chamber where Tascela has bound Valeria to an altar, but is caught in a steel trap helpless to save Valeria. At this point Tolkemec enters the chamber, having become a wild man during his exile in the catacombs, and uses a magical wand to kill Tascela's followers. Desperate for assistance, Tascela frees Conan. Conan defeats Tolkemec while Valeria frees herself and kills Tascela with a dagger thrust to the heart. With the last inhabitants of Xuchotl slain, Conan and Valeria depart the dead city.