It's apparently difficult to date the original Conan stories, because many of them were written at more or less the same time and then submitted all at once to Weird Tales and printed whenever the editors decided. According to Wikipedia, though, Scarlet Citadel was published in January 1933, after the original Phoenix on the Sword.
In this story Conan is still the king of Aquilonia, and is embroiled in a fierce battle with his former ally King Amalrus of Ophir and Strabonus, the king of Koth. His 5,000 soldiers are brave and fight their best, but eventually they are overpowered by the 30,000 soldiers lying in wait. Conan is captured and taken to the scarlet citadel.
It is in the scarlet citadel, located in the city of Khorshemish in Ophir, that Conan meets Tsotha, a sadistic evil wizard who has struck a deal with the traitorous nobles.
That's the setup. Conan is captured and held imprisoned by a dangerous magic user. It sets the stage for what Robert E. Howard does best: weave impossibly intricate tales about magic and mundane items without actually writing more than a sentence. Howard excels at planting ideas into your head with but a few choice words. A whole magic system is invented in your mind with just one simple trick by Tsotha. A kingdom's history is written with the barest mention of a mysterious treasure. It's efficient and evocative writing, the stuff of a good D&D campaign, with seeds of stories and histories planted with everything encountered.
Tsotha isn't the only one dwelling in the citadel, of course, and as any good villain does he wanders off before killing his captive properly. Conan meets a man who claims to have known the king when he was still but a pirate.
Conan, a pirate?
Yes, it's revealed, in passing, to the wide-eyed reader of 1933 that Conan, the unconventional king of Aquilonia, was once a pirate. And just like that, Howard opens a whole new world of possible stories (and he does, indeed, later deliver).
The sense of discovery is what drives this story. Sure, there's betrayal and danger, a monster, an evil wizard, and ghosts from the past. But most of all, it's the outrageously subtle hints of a wider world that makes the story so gripping.
As is pretty common with Conan stories, this one could be converted to a D&D campaign relatively easily. It has all the elements of a dungeon, and an underlying story that unravels as new elements of the scarlet citadel are discovered.
As the greater story of Conan goes, I admit that this is not the story I'd expected to be the big followup to the first. The audiences of 1933 must have wondered what exciting adventure this strange king was going to get up to next, and how surprised they might have been to find that the third tale in publication order found Conan at a much younger age, as a common thief, and not a very good one at that. That, of course, I must save for next month. In the mean time, you can (and should!) read Scarlet Citadel for yourself on gutenberg.net.au.