They recorded a few demos in the early 90s before releasing their debut album Dark Metal in 1994, which featured Andreas Classen on vocals.
On their second full-length album Dictius Te Necare (Latin: You must/should kill yourself), Classen was replaced with Rainer Landfermann on vocals (known as the bass player in the German death metal band Pavor).
Guido Meyer de Voltaire, the vocalist from Schatten aus der Alexander Welt and Mein Weg, is also well known with his band Aardvarks.
Andreas Classen, vocalist on Dark Metal also did vocals for Shining (primary vocalist Niklas Kvarforth also provided vocals for Bethlehem on the album A Sacrificial Offering to the Kingdom of Heaven in a Cracked Dog's Ear), Dark Creation, Paragon Belial, Made of Iron, Kadathorn, and Darkened Nocturn Slaughtercult.
In 1998 Bethlehem collaborated on the soundtrack for the American underground movie Gummo with the tracks "Schuld Uns'res Knöcherigen Faltpferds" and "Verschleierte Irreligiösität".