"Kelly the Conjure-Man" was sent to Texas Company (Texaco Star) on June 4, 1931, and later rejected.

"Black Canaan" was inspired by the legend of Kelly the Conjure-man. In late 1930, Howard wrote a long letter to H. P. Lovecraft concerning the history and lore of the South and Southwest. He mentions the Scotch-Irish settlement of Holly Springs, Arkansas, where his grandfather William Benjamin Howard settled in 1858. After recounting some of the local history, Howard goes on to write (letter #145):

Probably the most picturesque figure in the Holly Springs country was Kelly the 'conjer man,' who held sway among the black population of the `70s. Son of a Congo ju-ju man was Kelly, and he dwelt apart from his race in silent majesty on the river... He lifted 'conjers' and healed disease by incantation and nameless things made of herbs and ground snake bones... Later he began to branch into darker practices... he black population came to fear him as they did not fear the Devil, and Kelly assumed more and more a brooding, satanic aspect of dark majesty and sinister power; when he began casting his brooding eyes on white folks as if their souls, too, were his to dandle in the hollow of his hand, he sealed his doom...They began to fear the conjure man and one night he vanished...

The same letter:

There were desperate characters living in the river-lands, white folks little above the negro in civilization, and much more dangerous and aggressive. They began to fear the conjure man and one night he vanished. Nor is it difficult to picture what happened in that lonely cabin, shadowed by the pine-forest — the crack of a shot in the night, the finishing stroke of a knife, then a sullen splash in the dusky waters of the Ouachita — and Kelly the conjure man vanished forever from the eyes of men.

Dr. Howard was born in the Ouachita River area in Arkansas, and REH had two pictures of the Ouachita River area.

In Howard's following letter (#152) from January 1931 to Lovecraft, he responds to the latter's suggestion that he make use of Kelly in his fiction:

I am glad my comments on the Southwest interest you, and I feel most highly honored, indeed, at the kind things you have said about my descriptions, etc. Kelly the conjure-man was quite a character, but I fear I could not do justice to such a theme as you describe. I hope you will carry out your idea in writing the story you mention, of a pre-negroid African priest reincarnated in a plantation negro. As for me handling this theme better than yourself, it is beyond the realms of possibility, regardless of any first-hand knowledge of background which I might possess. I lack your grasp on cosmic thoughts, your magnificent imagination, your command of rhetoric and vocabulary, your power to invest the unreal with a grisly reality — in short, I am a mere novice where you are a master. I hope you will write this story some time, and if any of my anecdotes of pine land and negro lore can be used in any way, or give you any ideas, you are more than welcome to them.

However, despite Howard's reticence, Kelly did begin to find a way into his writing.

In the letter in which he first mentions Kelly, Howard thanks Lovecraft for putting him in touch with William B. Talman. Talman was an employee of Texaco and wrote to Howard concerning contributions to his company periodical, The Texaco Star. Howard's article "The Ghost of Camp Colorado" appeared in The Texaco Star a few months later in April 1931.

It was also in 1931 that Howard submitted a follow-up article to The Texaco Star entitled "Kelly the Conjure-Man." The article begins:

About seventy-five miles north-east of the great Smackover oil field of Arkansas lies a densely wooded country of pinelands and rivers, rich in folklore and tradition. Here, in the early 1850s came a sturdy race of Scotch-Irish pioneers pushing back the frontier and hewing homes in the tangled wilderness.
Among the many picturesque characters of those early days, one figure stands out, sharply, yet dimly limned against a background of dark legendry and horrific fable -- the sinister figure of Kelly, the black conjurer.

— Robert E. Howard, Kelly the Conjure-Man

From there Howard expands on the story of Kelly as recounted to Lovecraft.

"Kelly the Conjure-Man" was rejected by The Texaco Star and only saw publication decades after Howard's death. However, a seed had been planted in Howard's imagination to germinate for several years. Eventually, Howard recast Kelly as Saul Stark in "Black Canaan."