The Phoenix on the Sword was a rewrite of his Kull story By This Axe I Rule which had been rejected for publication. Howard often cannibalized his own work & used it it later stories. I really enjoyed his opening to The Phoenix on the Sword.
"KNOW, oh prince, that between the years when the oceans drank Atlantis and the gleaming cities, and the years of the rise of the Sons of Aryas, there was an Age undreamed of, when shining kingdoms lay spread across the world like blue mantles beneath the stars - Nemedia, Ophir, Brythunia, Hyperborea, Zamora with its dark-haired women and towers of spider-haunted mystery, Zingara with its chivalry, Koth that bordered on the pastoral lands of Shem, Stygia with its shadow-guarded tombs, Hyrkania whose riders wore steel and silk and gold. But the proudest kingdom of the world was Aquilonia, reigning supreme in the dreaming west. Hither came Conan, the Cimmerian, black-haired, sullen-eyed, sword in hand, a thief, a reaver, a slayer, with gigantic melancholies and gigantic mirth, to tread the jeweled thrones of the Earth under his sandaled feet."
--The Nemedian Chronicles
The Phoenix on the Sword is also one of the more quotable of the Conan stories. Here are just a few of my favorites.
"I had prepared myself to take the crown, not to hold it."
"A great poet is greater than any king."
"Rush in and die, dogs - I was a man before I was a king."