The Shadow Kingdom is the first Kull story and is set in Howard’s Thurian Age. Howard completed an early form in the summer of 1927, rewrote it later that summer, and sold the story that September for $100, payable on publication. Weird Tales eventually published it in August 1929.

In a September 1927 letter to Tevis Clyde Smith, Howard wrote that he had enjoyed writing the story more than any prose he had previously written and described it as dealing largely with “primitive psychology.” In an October 1928 letter to Harold Preece, he described the setting as a mythical antediluvian empire contemporary with Atlantis.

Howard continued to refer to the story in later correspondence. In 1933 he arranged permission from Weird Tales for a proposed anthology reprint. Later, discussing the Kull stories with H. P. Lovecraft, Howard said that the three Kull stories he had written seemed to arrive in his mind fully formed and without conscious planning, which was why he doubted he could deliberately reproduce the same effect.

The first we learn of the story from the letters is when he wrote Tevis Clyde Smith, circa mid- to late-September 1927 (letter #054):

P. S. Since writing you that other letter I’ve sold another mss. I got a hundred dollars for it; that is, I am to get it on publication. I don’t know when it will be published or whether you’ll like it or not. I enjoyed writing it more than any piece of prose I ever wrote. The subject of psychology is the one I am mainly interested in these days. The story I sold before this3 was purely a study in psychology of dreams and this ms. deals largely in primitive psychology. I don’t know whether they’ll publish it as a serial or as a “complete novel.”

The first story mentioned is "The Shadow Kingdom", the second is "The Dream Snake".

Howard mentions the story in a letter (#086) to Harold Preece, dated October 20th, 1928:

All my views on the matter I included in a long letter to the editor to whom I sold a tale entitled “The Shadow Kingdom,” which I expect will be published as a foreword to that story — if ever. This tale I wove about a mythical antediluvian empire, a contemporary of Atlantis.

Howard mentions the story in a letter (#107) to Tevis Clyde Smith, circa April 1929.

Farnsworth said he intended publishing a sonnet in the next issue after that and then “The Shadow Kingdom” which is a $100 story, and after that a shorter story.

He mentioned it again in a letter (#123) from circa March 1930:

I received a letter from Farnsworth today accepting my “Kings of the Night” — $120, on publication of course. I rather expected him to take it for the new magazine, as it’s full of action but has no really weird touches. However he accepted it for Weird Tales; possibly because the central figure is Kull of Atlantis, featured in “The Shadow Kingdom” and “The Mirrors of Tuzun Thune.” It was rather a new line for me, as I described a pitched battle.

and again to Harold Preece in a letter (#144) in October or early November 1930:

But to return to the Mediterraneans of the Isles, where these tribes remained a race apart longer than anywhere else. These aborigines are popularly known as Picts, and by this name I have designated them in all my stories — and I have written a number in which I mentioned or referred to them — “The Lost Race,” “The Shadow Kingdom,” “The Mirrors of Tuzun Thune,” “The Dark Man,” “Kings of the Night,” to say nothing of several which I have not marketed.

On February 20th, 1933 Howard wrote (letter #235) to Mr. August Lenninger regarding 'The Shadow Kingdom':

Dear Mr. Lenniger:

Here are the copies of “The Shadow Kingdom.” I assume that you have arranged with Weird Tales for the reprint rights. That magazine owns all rights to the story. Please let me know by return mail what arrangements you have made with the magazine company. I enclose a stamped envelope for your convenience.

E. Hoffmann Price wrote Howard telling him that he and Mashburn were attempting to promote a sort of anthology of weird tales (see letter #173).

Howard later informs Mr. Lanninger that he has permission to allow the story to be published in the proposed anthology (letter #239):

This is to inform you that I have the permission of Weird Tales to allow “The Shadow Kingdom” to be published in the proposed anthology.

Lovecraft commented on Howard's Kull stories (this letter does no longer exist) and in a letter (#294) Howard says:

Thanks for the kind things you said about the Kull stories, but I doubt if I’ll ever be able to write another. The three stories I wrote about that character seemed almost to write themselves, without any planning on my part; there was no conscious effort on my part to work them up. They simply grew up, unsummoned, full grown in my mind and flowed out on paper from my fingertips. To sit down and consciously try to write another story on that order would be to produce something the artificiality of which would be apparent.

 Howard is acknowledging only the three stories published in Weird Tales: “The Shadow Kingdom,” August 1927; “The Mirrors of Tuzun Thune,” September 1927; and “Kings of the Night,” November 1930.

This story is also referred to after Howard's death, in Fantasy Magazine, September 1936 in their 'In Memoriam':

Always a keen student of Celtic antiquities and other phases of remote history, Mr. Howard began in 1929—with “The Shadow Kingdom,” in the August Weird Tales—that succession of tales of the prehistoric world for which he soon grew so famous.

And E. Hoffmann Price brings the story up in his 'Diablerie' from May 1944 about Robert E. Howard:

Howard lived in a realm of wonder and fantasy. After hearing my reasons for considering certain early yarns, such as “Kings of the Night,” “Mirrors of Tuzun Thune,” “Shadow Kingdom,” and the “Brule the Spear Slayer” epoch, far superior to the Conan series, he agreed and said, “I dreamed them, so they’re naturally more realistic than those I deliberately wrote.”

He does the same for The Ghost, published in May 1945 by W. Paul Cook.

This can’t be the man who wrote “The Shadow Kingdom,” or “Kings of the Night,” this can’t be the man who composed the tremendous lines at the climax of “Sowers of the Thunder”: poetry in the form of prose, and with all the ring of Elizabethan drama.