The Moon of Skulls is a Solomon Kane story set in Africa. Howard first sent it to Jungle Stories; Macfadden Publications returned the manuscript on August 15, 1929, explaining that the magazine had been transferred to another publisher. The story was later accepted by Weird Tales and published in two parts, in June and July 1930. Howard received $200.

The story follows Kane in search of the Englishwoman Marylin Taferal, who has been kidnapped and sold to Barbary pirates, and leads him to the hidden city of Negari and its ruler, Nakari. Howard mentioned the forthcoming first installment in a letter to Tevis Clyde Smith circa February 1930. After publication, he told H. P. Lovecraft that he was pleased Lovecraft had liked the story.

The story was sent to Jungle Stories, but they returned it on the 15th of August 1929 by Macfadden Publications:

Dear Mr. Howard:

Referring to your manuscript, (as below) which you recently submitted to us for Jungle Stories Magazine, we regret to inform you that we will be unable to use this material for the reason that the magazine in question will not be published by us, but has been turned over to the Good Story Publishing Company, Room #1119, 25 West 43rd Street, New York City, a group of magazines published and edited by Mr. Harold Hersey.

We are accordingly returning the above mentioned material to you enclosed herewith, and would suggest that if you are still interested in having it considered for the publication above mentioned that you get in touch with the Good Story Publishing Company, direct, at the address given.

With kind regards and best wishes, 
Yours very truly,
MACFADDEN PUBLICATIONS, INC
Manuscript Bureau.

It was later accepted by Weird Tales and published in two parts. Howard got $200 for the story.

Kane goes to Africa on the trail of an English girl named Marylin Taferal, kidnapped from her home and sold to Barbary pirates by her cousin. When he finds the hidden city of Negari, he encounters Nakari, "the vampire queen of Negari".

In a letter (#121) circa February 1930 to Tevis Clyde Smith he wrote:

Next issue appears my “A Song Out of Midian” for which I’ve already received the advance page; and he tells me he is going to give me the cover design for the June issue in which will appear the first installment of “The Moon of Skulls”.

Lovecraft told Howard that he liked the story and in a letter (#137) to HPL circa August 1930, Howard wrote:

I am glad that you liked “The Moon of Skulls” and hope my future efforts meet your approval. And I am highly honored to know that Mr. Long and Mr. Clark Ashton Smith have noticed my efforts. Both are writers and poets whose work I very much admire, having carefully preserved all of their poems (as well as all of yours) that have appeared in Weird Tales since I first made my acquaintance with the magazine.