Thulsa Doom first appeared (as Thulses Doom) at the end of the short story "Delcardes' Cat" by Robert E. Howard, which featured the character Kull as the protagonist. Howard later edited the text to include foreshadowing/references to Thulsa Doom (as he had been rechristened) throughout the story and changed the title to The Cat and the Skull to reflect this.

Thulsa Doom is described by Howard in "The Cat and the Skull" as having a face "like a bare white skull, in whose eye sockets flamed livid fire". He is seemingly invulnerable, boasting after being trampled by one of Kull's comrades that he feels "only a slight coldness" when being injured and will only "pass to some other sphere when time comes".