Red Blades of Black Cathay was written as a collaboration between Robert E. Howard and Tevis Clyde Smith. It was first published in Oriental Stories in the February/March issue of 1931. It was accepted in July 1930.

The story is an adventure set during the Crusades with Genghis Khan, flashing swords, mighty battles, lots of adventure, and lurid descriptions. 

In a letter (#136) Howard wrote to Smith circa July 1930 he says:

I haven’t heard from our story but that’s not unusual, seeing that I haven’t heard from a story I sent to Weird Tales some time before I sent the other; the editor may be taking a vacation or something.

and in the same letter:

I quote from a letter from Farnsworth: “I am very well pleased with ‘Red Blades of Black Cathay,’ and may use this as the cover design story for our third issue of Oriental Stories. We can offer you $118 on publication for it; and also $118 for “Wings in the Night” for Weird Tales. This is at our regular rate of 1c a word.”

Later, in another letter (#146) to Smith, circa November 1930, Howard says:

I quote from Farnsworth’s last letter: “‘The Voice of El-Lil’ is tied for first place with ‘Strange Bedfellows,’ in the letters and votes received so far for the first issue of Oriental Stories. This augurs well for the popularity of ‘Red Blades of Black Cathay’ and ‘Hawks of Outremer,’ which I think are much more striking. Von Gelb has galley proofs of ‘Red Blades of Black Cathay’ and is working on a cover design. Joseph Doolin will do the black and white illustration.”

While waiting for Farnsworth Wright to pay for the publication Howard writes (letter #154) to Smith late-January 1930, showing some of his humor:

I’ve delayed writing you, hoping I’d receive the check for the Cathay hooey, but the devil only knows when we’ll get it. I got a letter from Talman of the Texas Company saying that he hadn’t seen my Camp Colorado article, but had an idea that the moguls had approved of it. I hope so. Talman praised our Cathay story highly and said he was sure the historical details were nine-tenths correct. I’m going to write him that you supplied the historical data, so if he finds an error he’ll blame it on you — he said lousily.

and in the same letter:

Orientals might possibly send the check for the Cathay story to you; if they send it to me, I’ll either bring it over, or let you know immediately. The devil only knows when we’ll get it.

He also wrote to Lovecraft (Letter #156 - cirka February 1931) telling him about his collaboration with Smith:

If you haven’t seen the latest Oriental Stories, let me know. I have some extra copies. It contains a story by Tevis Clyde Smith and me, which you might possibly entertain an idle half-hour with, though I fear it isn’t anything to brag about.

Wilfred B. Talman had already read the story and sent his appraisal. In a letter to him (letter #157 - cirka February 1931) Howard thanks him for his kind words and says:

I can hardly find words to express my appreciation for your interest in “Red Blades of Black Cathay”. Both Mr. Smith and I are highly gratified by the compliments you paid the story, and hope that future efforts will meet with your approval. I also appreciate very much your writing to Mr. Wright in commendation of the tale. I hope that our details were as nearly accurate as you say — we were rather uncertain on a few points — medieval Oriental history being so sketchy. I must admit that there was a weak point in the story — from my study of Genghis Khan I feel certain he would never have allowed Godric to reign as an independent and equal king; he would have destroyed the empire of Black Cathay entirely first. But we had to have it that way, in order to allow Godric to live and realize his ambition. You being a writer yourself, understand such difficulties. Of course we took a great deal of liberties in regard to the actual conquest of Black Cathay, but I suppose that comes under the head of fictional license or something. By the way, the name “Subotai” is the Mongol term for buffalo.