The Shadow Kingdom (1929) by Robert E. Howard

   The Shadow Kingdom is considered by many to be the first modern Sword and Sorcery tale. It was the first published story about King Kull, an Atlantean renegade who became king of the prehistoric kingdom of Valusia. The Kull tales were Howard's first attempts to create a fully-realised fantasy world and it was from Kull's Pre-Cataclysmic Age that Conan's Hyborian age was born.
   Despite their similar occupations, Kull was a vastly different character than Conan. Kull was a brooder, constantly preoccupied by dark thoughts regarding the nature of reality. Having fought hard to win the kingship, he was rather uncomfortable and distrusting on the throne (with good reason as it turns out). In stark contrast to Conan, Kull did not have the least interest in women. Kull, perhaps mentally battered by a hard life, was a loner. His world was dark and shadowy, with a much murkier feel than the later Hyborian Age.
   The Shadow Kingdom begins with a finely written parade of Kull's army. It brilliantly introduces Kull's kingdom and his place in it. Later, Kull receives a message from Ka-nu, the Pictish ambassador, requesting that Kull meet him alone later that night. Kull, being a distrustful sort, taunts Brule, the bearer of the message. It seems that Atlanteans and Picts are tribal enemies, so the two share an immediate dislike. Despite that, Kull agrees to go.
   Kull finds Ka-nu feasting, hanging out with Pictish ladies and having a fine time. He gets right down to business though and warns Kull that his life and his very kingdom are in great jeopardy. He does not reveal what the danger is, but he promises to send a warrior later that night who will reveal the danger to him and provide definite proof.
   Of course the warrior is none other than Brule. Brule leads Kull into a secret passage that Kull was completely unaware of, and there shows Kull the unconscious bodies of guardsmen whom Kull had just seen moments before outside his door. Soon Kull learns the terrible truth, his palace has been infiltrated by evil Serpent Men; ghastly creatures that can magically take the form of anybody they wish. It seems that these Serpent Men have been hanging out in Valusia for years, often killing kings and taking their place. That is, of course, what they plan to do with Kull.
   Together, Kull and Brule fight to wreck the plot of the evil Serpent Men and expose them. During the course of the adventure Kull and Brule learn to trust each other and by the end are true friends. Kull comes to feel a sense of kinship with Brule, finding in him a fellow tribesman in an alien culture. Like Brule, Kull is a barbarian. Kull took the crown of Valusia by force and so is forever set apart from the decadently civilized people he rules. In Brule, Kull has at last found somebody he can rely on.
   The Serpent Men are a truly great creation. Ancient beings who can take the form of anybody they wish, they are the perfect villains to oppose the already paranoid Kull. Their existence validates all his fears. Indeed, they are such a great invention that the conspiracy-theory writer David Icke seems to have adopted them wholesale, renaming them Reptilians and claiming they are even now impersonating  just about avery political figure he can think of.
   With plenty of Howard's fast-paced action and dark atmosphere, The Shadow Kingdom is one of his finest stories. It can be found in Kull: Exile of Atlantis and The Best of Robert E. Howard, Volume 1: Crimson Shadows