“Red Shadows” was REH’s first published Solomon Kane story (Howard’s original title was “Solomon Kane”). It tells a tale of wide scope, one which takes place over many years and in many countries. It’s a tale of unrelenting dogged persistence as Kane spends years of his life seeking to avenge the death of a complete stranger.

First published in Weird Tales, August 1928. Howard got $80 for this story. The story was also sent to Argosy, but it was rejected.

In a letter (#062) to Tevis Clyde Smith in the week of February 20th, 1928, he talks about this story which was originally titled simply 'Solomon Kane':

Strange thing: I had a long mss. with the Argosy-Allstory and last night I dreamed that I got it back together with a long personal letter from the editor, written in pen and ink. Sure enough I did. He said in some places the story was “very good” and in some places “rotten!” He says that I have the “stuff” if I “get steered right” so therefore he is giving me the reasons it was turned down, in detail. He did, very concisely and very clearly. He says as the setting was the Middle Ages, I had too much “Eugene O’Neill jungle stuff” in the story. (He’s not accusing me of plagiarizing.) The main reason for non sale was “unexplained miracles.” The reason for this is, I wrote this story for the Weird Tales originally and then decided to try my luck with Argosy-Allstory, just as it was. So, if a despised weird tale, whose whole minor tone is occultism, can create that much interest with a magazine which never publishes straight weird stuff, I don’t feel so much discouraged. He apologizes for having kept the mss. so long, saying that he wished to write me a personal letter and therefore kept the mss. on his desk two weeks before he found time; he says they have been getting about 100 mss. a day.

And in another letter (#066) circa March 1928, we learn that he has sold the story to Weird Tales:

The Weird Tales took that mss. the Argosy editor commented upon, offering me $80. The Weird Tales editor took it in its original form, for I didn’t change it any, in spite of the defects pointed out by the Argosy editor, and says that he thinks he’ll give me front page and cover illustration. He asks me to change the title “Solomon Kane” however and I can’t seem to think of a good title.

Circa June 1928 Howard writes a handwritten letter (#074) to Tevis telling him:

Next month if nothing happens the Weird Tales publishes my “Red Shadows” which according to the announcement is “Red Shadows on black trails — thrilling adventures and blood-freezing perils — savage magic and strange sacrifices to the Black God the story moves swiftly and without the slightest let-down in interest through a series of startling episodes and wild adventure to end in a smashing climax in a glade of an African forest. A story that grips the reader and carries him along in utter fascination by its eery succession of strange and weird happenings.” The announcement does it a fair amount of justice I suppose.

And he also writes Harold Preece about his story circa June 1928:

This issue of Weird Tales there is an announcement of a story scheduled for next month, “Red Shadows,” which I submitted to Argosy-Allstory under the title of “Solomon Kane,” and was rejected. The announcement gives it justice in a fair manner. Also a rime in this issue, “The Gates of Nineveh.” Read it; it’s good.

In 1930, circa October Howard again mentions 'Red Shadows' in a letter (#143) to H.P. Lovecraft:

What a black and bloody land the West Coast of Africa is! The chronicles of the fleeting black empires read like nightmares. I tried, in “Red Shadows” to create a slight sense of the bestial inhumaness of the country, but failed utterly. It must be something that a man must see in order to get a complete idea of it. Some day I intend to go and see it at first-hand.

And we're in for a treat when Howard writes a letter to Alvin Earl Perry, circa early 1935:

The first character I ever created was Francis Xavier Gordon, El Borak, the hero of “The Daughter of Erlik Khan” (Top-Notch), etc. I don’t remember his genesis. He came to life in my mind when I was about ten years old. The next was Bran Mak Morn, the Pictish king (“The Kings of the Night”, etc., Weird Tales). He was the result of my discovery of the Pictish race, when reading some historical works in a public library in New Orleans at the age of thirteen. Physically he bore a striking resemblance to El Borak. Solomon Kane (“Red Shadows”, etc., Weird Tales) I created when I was in high school, at the age of about sixteen, but, like the others I have mentioned, several years passed before I put him on paper. He was probably the result of an admiration for a certain type of cold, steely-nerved duelist that existed in the sixteenth century.