I used the idea that Humans, Dwarves, Halflings, Orcs, and Goblinoids were all bred as slaves from apes. The race that did it was called the Neas, and looked 9-foot tall cross between a man, a crayfish, and a cuttlefish, and was engaged in an intergalactic war with the hedonistic, bloodthirsty ancestors of the Elves. The Gnomes has arrived separately, but were subsequently enslaved by the Neas. The Neas controlled their slaves with a powerful hallucinogen used as a reward for work. After thousands of years, the dreams of the slaves became so powerful they were able to actualize them, giving birth to magic (yes, I had Humans originally create magic, not Elves). The Elves created agents among the Neas' slaves, and provoked a rebellion that ultimately destroyed the Neas. The Elves quickly became addicted to the Neas' hallucinogen, and learned magic. Eventually the hallucinogen became incorporated into the genetic code of the various races. A space-faring civilization incorporating all the races emerged. It was destroyed by a virus that manifested the nightmares of the humanoid races. Horrible monsters were born, necromancy was created, and races like the Drow emerged. Warfare and social strife reached genocidal levels, and finally an Ice Age obliterated almost all evidence of the previous civilization.
When the campaign started, the PC were all humans in society very similar to Renaissance Europe, were magic was illegal and the demi-human races were considered the stuff of folklore. Gradually they came to encounter other races in out-of-the-way places, and eventually found out about the secret history of their world.