How to Obtain Your Warlock's Succubus in World of Warcraft, Part 1

You've gotten your Voidwalker and he's good, but he gets in the way. He has a strange genie-like quality...what more is there to offer? The evil Succubus! This devious gal may not be the physical brute the Voidwalker is, but she has a few tricks up her sleeve your Blue companion can't even get near. This quest is different for Alliance and Horde, so we'll look at Alliance for now.
Get Started
Step 1When you hit level 20, go visit Gakin the Darkbinder in The Slaughtered Lamb (Warlock trainer central) in the Mage Quarter of Stormwind. He will start you on the quest to obtain your Succubus, beginning with a trip to the Barrens.

Step 2Find an escort of level 30+ if you can. If not, you'll just have to summon your Voidwalker, strip (so your armor doesn't get damaged) and run the gauntlet. Fly to Menethil Harbor and take the boat to Theramore Isle. If you don't have the Menethil Flight Point, you'll have to leg it.

To Get to Menethil Harbor
Step 1Go to Ironforge, head out the front gate and down the path.

Step 2Take a left at before you hit Kharanos; this will take you east.

Step 3
  Take the North Gate Pass into Loch Modan, then heart North again into Algaz Pass. This will take you into the Wetlands which is contested territory if you're on a PVP server.

Step 4Follow the path through the Wetlands. This will take you straight to Menethil Harbor.

Step 5Watch out for Crockolisks on the roadside.

Step 6Get on the boat on the far left when you hit the harbor. This will take you to Theramore Isle. There is an NPC on each end of the dock to tell you where the boat is going. The boat in the middle does not leave.

Theramore, Dustwallow and the Barrens
Step 1Craft a Soulstone and store your Soul, make sure you've got your Voidwalker and are wearing nothing breakable, then run through Dustwallow until you hit the junction for the Barrens. If you are on a PVP server, be on your guard! The Barrens is Horde territory! If you get attacked on the road, let your Voidwalker soak the trouble and keep on running. If you die, use your Soulstone and bring your Voidwalker back immediately!

Step 2Head to the right when you hit the first junction on South Gold Road. This will take you North.

Step 3Look for Camp Taurajo on your left, just north of the entrance to Mulgore. If you have a coordinate system, you will find Takar the Seer at 49, 57. Look for a tent next to a tree.

Step 4
  Talk to Takar and accept his quest to get the Heartswood. Tune in for Part 2!