It's not like Tieflings are exclusively from the Hells, they simply have someone in their family who was. They've been around pretty much always, just not commonly in such a large group. If I recall, a bunch of arrogant High Elves were the first to summon devils to make stronger offspring i.e. Tieflings. - got a little out of hand and their entire civilization was burned to the ground eventually though.
