"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:

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...

— Robert E. Howard, Letter to H. P. Lovecraft

The Black Canaan by Greg Staples

In Howard's following letter to Lovecraft, he responds to the latter's suggestion that he make use of Kelly in his fiction; "Kelly the conjure-man was quite a character, but I fear I could not do justice to such a theme as you describe." 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."

On March 6, 1935, Howard writes to Emil Petaja (letter #309) tells a bit more about the story:

Glad the ms. proved satisfactory. Haven’t located that last page yet, but know it’s around here somewhere. The yarn on the back of the pages is — if I remember correctly — a weird story called “Black Canaan” based on a real life character with a realistic background (though the latter considerably altered) the region actually known as “Canaan” in southwestern Arkansas, between Tulip Creek and the Ouachita River, not far from the ancestral home of the Howards. The story hasn’t found a market so far.

As “Black Canaan” was originally sent to the Kline agency in September 1934, and a notation in the Kline records shows a rewritten version received in November. It is currently not known what manuscript Howard is referring to here.

And to August Derleth, May 9, 1936 (letter #349) Howard writes:

Ignore my forthcoming “Black Canaan”. It started out as a good yarn, laid in the real Canaan, which lies between Tulip Creek and the Ouachita River in southwestern Arkansas, the homeland of the Howards, but I cut so much of the guts out of it, in response to editorial requirements, that in its published form it won’t much resemble the original theme, woven about the mysterious figure of Kelly the Conjur-man, who was a real character, back in the seventies — an ebon giant with copper rings in his ears and a gift of magic who came from nowhere and vanished into nowhere one dark night when the owls hooted in the cypresses and the wind moaned among the nigger cabins.