I assume most cultures have always believed in some form of glorious, heaven-like place where the souls of loved-ones go after they die - if for no other reason than to appease the grieving.
But who was the first to come up with the concept of Hell?
Did Heaven and Hell always go hand in hand or was this a later concept used as a threat to the unholy?
I’d say wrong on both counts. Some cultures believe in reincarnation. Ancient Greeks believed in a fairly mundane afterlife, except for those few who pleased or annoyed the gods - not really related to good or evil.
A history of the Judeo-Christian hell:
My ex-wife!
Good point about reincarnation, but there’s nothing mutually exclusive about rebirth and hell. Many Buddhists believe that you can be reborn into a hell realm after death, just as you can be reborn into a heaven realm.
Your time in heaven or hell is limited, however, because “all conditioned things are impermanent,” so you eventually “die” in heaven or hell and are reborn yet again. Eventually you may return to the human or animal realms, and the process is repeated ad infinitum or until you achieve Nirvana.
Of course, there are significant differences between this kind of impermanent hell and the eternal torment of Judeo-Christian-Muslim hell, both in duration and in purpose, but still, hell is hell.
Nametag: good points.
Walloon: So, in a nutshell - Christians may be the discoverers.
Omnipresent: I’m sure there is a story there. Later.
Straight Dope Staff Report: Who Invented Hell?
Nope. I think the most common beliefs are/were that deceased either lived a live fairly identical to terrestrial life, either lived as shadows without happiness or clear identity in some not so pleasant place.
I hadn’t realized we discovered it. Are there tours? 
Any chance to get the cold drinks/ice concession?
I disagree. Buddhists don’t have one heaven for the good and one hell for the evil. For one thing, there isn’t any morality to the system, merely cause and effect – you do bad, you go to a hell, you do good, you go to a heaven. For another thing, there are many multiple heavens and hells! Essentially, a heaven can be perceived as a place that’s better than Earth, and a hell a place that is worse. I think that’s a lot different than the concept of Judgement, residing with God or with Satan and his minions.
The reason I want to make this distinction is that I would not want the OP to think that, for some reason, belief in heaven and hell is somehow ‘universal’ or nearly so (it’s not) or that this would somehow give proof to the idea that the Christian dual afterlife is how things really are, which is the vibe I get.
Curiously, dmark, the idea of Hell seems to have come first, in a way. The Greek Hades (which is one word for Hell used in the Bible, itself) did not have a real notion of Heaven, though it did have judgement of the soul; even the Elysian Fields were considered worse than being alive. Those that honored the gods were rewarded, and others punished, but your rank in Hades wasn’t supposed to be the focus for your life as it is in Christianity. Life was supposed to be the focus.
Not all cultures have Heaven, as hard as that may be to believe. It’s a nice idea, but hardly universal. The entire idea of God(s) having love for humans, or being perfect, isn’t universal, either. Many cultures have had gods that would seem to us as cruel, tyrannical, even evil. There are all kinds of theories why, but the idea of a personal God – rather than a distant God, communicated with via complex rituals – is recent.
I think you’d find a study of ancient Middle Eastern, as well as Greek and Egyptian, religions and beliefs very informative.
fluiddruid, I don’t think we’re communicating clearly.
'Tis true. You’ll notice I said
I didn’t say there was only one of each, though perhaps I could have been clearer. In classical Buddhist cosmology, there are four planes of existence comprising 31 spheres of existence. Above the human plane are the realms of devas and Brahmas. All these are accessible through meditation as well as through rebirth. Below humans are the animals, hungry ghosts, and a series of hell realms.
I’m not sure what you’re saying here. “Bad” and “good” are moral judgments. It’s true that there is no personal judge who decides where you go, as in the Christian afterlife, and that kamma operates on a cause-and-effect basis, as you say. But that doesn’t exclude morality; the Buddha spoke quite often about morality (sila) as it relates to kamma. Sila is one of the divisions of the Eightfold Path and is also a paramita (one of the Ten Perfections).
Maybe not as different as you’d think. Granted, there is no Judgment. But in a Buddhist heaven, you might well reside with a god, possibly lots of them! And some of the Buddhist hell realms involve being attacked by what Christians might call demons.
And remember, Christian hell is not universally conceived as “one place”; to wit, Dante’s circles of hell. And Cecil’s column lists at least two, “Sheol” and “Gehenna.”
Agreed. I tried to make this clear:
Maybe my little “hell is hell” line confounded things. And here I thought I was being clever. That’ll show me. 
Our modern conception of the afterlife owes a great deal to Dante Alighieri’s Divine Comedy (Inferno, Purgatorio, Paradiso). The Inferno, which is (more-or-less) a description of hell, is a fascinating read. I heard it was once “required reading” for all Catholic school students.