Nostalrius Begins - Quality wow vanilla realm (1.12)

So I am seeing warlocks at level 22 getting the succubus, I am level 29 and I still can't start the quest, am I missing a quest somewhere to start it?

Try going to the warlock trainer in Stormwind, he should have a quest for you, it's level 20 quest for Succubus.
You'll need to go to the barrens.