Thulsa Doom was originally created by Robert E. Howard as an "eternal foe" for his second most famous barbarian hero, King Kull of Atlantis. Doom only made one appearance, in the short story The Cat And The Skull, but the story suggested that this was not the first time Kull and Thulsa Doom had met in battle. Small wonder then that Thulsa Doom was chosen to be Kull's chief antagonist when the adventures of Kull were adapted and expanded upon by Marvel Comics in the 1970s.
This second version of Thulsa (who you can read a full history of here) was a lich - a necromancer whose power allowed him to defy death and be continually reborn. This allowed him to continue on, long after Kull's death, to plague other heroes (including Conan The Barbarian and Red Sonja) in the world of what became known as Hyboria after the fall of Atlantis.
The third version of Thulsa Doom is undoubtedly the best known. Portrayed by James Earl Jones in the first Conan The Barbarian movie, this version of Doom is a charismatic cult leader and reportedly a powerful sorcerer. This take on Doom seems to be much closer in personality and power to Conan's arch-enemy, the wizard-priest Thoth-Amon. Presumably they decided to use the name of Thulsa Doom for their villain because they had bought the rights to the entire REH library and it just sounded better.
The fourth and final version of Thulsa Doom was created by Luke Lieberman. A filmmaker by trade, Lieberman holds the film rights to the Thulsa Doom name and has been attempting to make a movie starring his version of the character for several years now. I think it best to quote Lieberman himself in describing his version of Doom.
We have a bold new vision for this character and plan to bring him back in a very Fresh and Big way. The film will take him back to his origins which involve the destruction of Atlantis. It is basically the Godfather meets Conan, exploring the paradox of Doom's character and confronting the deep inner conflict - oh and there will be monsters, explosions and fight scenes of course!
The Sonja Vs Doom Series I am writing with Peter [David] will introduce the younger Thulsa, along with reintroducing the more familiar, and older version. It will have some connection to the Conan Film, as Doom will be interested in the "Riddle of Steel" but beyond this we are forging into new territory.
Thulsa is a fascinating and complex character, his horrible charisma, his villainous sincerity. Thulsa Doom long ago sold his soul for power - he knows what the moral choices are, he is just beyond Good and Evil as it were.This version of Thulsa Doom, described by Lieberman as "the ultimate anti-hero" has primarily appeared in the pages of various Red Sonja comics, originally appearing for the first time in the Red Sonja vs. Thulsa Doom mini-series. He later returned, attempting to overthrow the gods themselves in Doom Of The Gods. He was next seen in the pages of Queen Sonja, attempting a mass sacrifice in order to bring about the end of the world at the behest of the god Set. Finally, and most recently, he appears in the new Red Sonja mini-series Atlantis Rises.