The Captain's Chest
This is all the Stranglethorn quests you had before, plus anything new that is available in Booty Bay at level 37. You probably also have Encrusted Tail Fins from Thousand Needles.
The place to start is right where we left off in the far north.
Scene 1: Kurzen's Mystery (level 37)
Although we've had it for a bit, we've avoided doing Kurzen's Mystery until now because it's a hard quest. At level 37, it's still a hard quest. But it's worth doing now. Leave the hunter camp west for the Ruins of Zul'kunda. Out of the four legends we need, two of them are here.
The Ruins of Zul'Kunda has a central road that passes through the heart of it. There are small outcroppings of trolls to both sides of the road until it reaches a downward slope with walls on both sides. On the left side of the road, NOT going down the slope, is where we will find our first legend. (It's actually the third legend, but who's counting?)
You will find the Third Troll Legend in the corner of the very last one of the "rooms" in this area. It looks like a huge stone tablet on its side. Be very careful of patrols in general in Zul'Kunda, and pull the room carefully, especially if you're alone. Sometimes a fellow quester will be in the area, which makes this much easier.
Return to the road through the ruins, and go down the slope. Shortly after the bottom of the hill, the wall on your right should end, and there will be a path behind it. (The road continues forward.) Wait for the patrol in the area, and kill those two trolls before they decide to gangbang you later. Then move very slowly and carefully up the path. Note that there is a troll above you to the left before you make it all the way up. Pull him back first if you can. At the top of the hill, turn left and in the distance you should see the Fourth Troll Legend. Pull just as you have to get this far, and you should be able to reach it without difficulty.
Leaving the area can be a bit more troublesome, as respawn typically catches up with you before you can exit. However, you want to try to return to the road, and follow it the rest of the way through the ruins and out to the beach. From there, swim out to the haunted isle to hunt down some water elementals.
Your next task is to get another troll legend. This one is underwater, and can prove troublesome if you don't know where it is. Leave the island due south, and swim underwater a bit so you can see the sunken ruins. The Second Troll Legend is OUTSIDE the wall of these ruins, on the northern edge toward the east, which means you should see it off to the left in front of everything else. What makes this irritating is that the ruins are filled with elite murlocs, but fortunately, with the right approach, you don't actually have to fight any of them because the legend is outside. If you do decide to fight the murlocs, these are the ones you need for Encrusted Tail Fins from Thousand Needles, however it's probably best to leave them alone unless you're here with a partner.
Swim back to shore and look for an Elder Saltwater Crocolisk. They are mixed in with the other crocolisks, and sometimes there aren't any out on the beaches at all, but either you'll find one eventually or you can clear out the normal crocs and wait for respawn. It should take everything you've got to kill one of the elders, since they're 38 elite, but you hopefully ought to be able to pull it off. Of course, that's not the smartest thing to do on a PvP server, so maybe you want to pass this one up or get some help.
Your final task is to get the First Troll Legend. (Wow, we're backwards.) You might even already have the first legend since it's in the back corner of the Ruins of Bal'lal, which should be fairly nearby the beaches you've been combing for crocolisks. This should be no worse than anything you've done in Zul'kunda, even if the trolls are packed together a bit.
Return to the Rebel Camp when you finish.
Quests completed: Water Elementals, Excelsior, Kurzen's Mystery, Return to Corporal Kaleb
Scene 2: Storming the Stockpile (level 38)
Before telling you to embark on this trip, I want to point out another quest you *might* have that you would want to be doing now. Every once in a while, Private Thorsen leaves the rebel camp and walks down the road to an open spot where he is supposed to meet Kurzen men as a double agent. They know he's actually working against them, so they jump him. If you save him, he will thank you and send you back to Sergeant Yohwa who will ask you to try to find the traitor in their midst. At that point, in the Kurzen Compound, there is a ledger in the bedroom of the two-story building for the follow-up quest Bookie Herod. Bring the book back, and you'll have a key to open a chest inside the Stockpile.
The Stockpile happens to be where we're going, so if you've got this quest series, great. The reason it hasn't been mentioned earlier is because Private Thorsen seems to leave the rebel camp so infrequently it isn't really worth waiting for him.
The Stockpile itself is the cave in the back of the Kurzen Compound, and the commandoes and headshrinkers you need for Special Forces are in the front half of this cave. Commandoes are always in stealth, so don't move too quickly. At level 38, you should be able to see them before they become a problem.
Eventually you will reach a long downward slope in the cave. That is your cut-off point for Special Forces. If you're intent on finishing the Bookie Herod quest line, head down the slope to the cavern at the bottom where the Kurzen elites and witch doctors are. Look about and you should eventually find a chest in this area that is unlockable with your key.
As you leave the Stockpile, one other thing you may want to do while you are here. It's easy to go a good long while without killing the Shadowmaw Panthers you need for the third mastery quest. Leave Kurzen's area due south, go past Zul'Gurub and the goblin lake, but stay to the east wall. You should reach an area filled with tigers and panthers…although you might not be able to see the panthers since they stealth. Bumble your way around until enough Shadowmaw Panthers find you so you can finish the quest. Stay away from Bhag'thera for now.
Quests completed: Special Forces, Bookie Herod (maybe), The Hidden Key (maybe), The Spy Revealed (maybe), Panther Mastery 3
Scene 3: Finishing Your Fights (level 38)
This scene is for people who are not alone. If you are alone, put this off until you can get some assistance. You have two goals that you can take in either order.
The follow-up to Special Forces is to kill Colonel Kurzen himself, who is at the very end of the cave. He is a level 39 elite, and you will NOT get him by yourself. You are welcome at any point you can get a group together to head back and finish off the Colonel. You will probably want at least 3 people for this battle, including one healer. Kurzen usually doesn't come without friends, and he takes a while to bring down.
The other item for this scene is to actually go down to where you were fighting the Shadowmaw Panthers before, and kill Bhag'thera. Bhag'thera is elite, between levels 38 and 40. You *might* be able to solo her, but it is strongly recommended you bring a partner. You will need to have Bhag'thera killed by the time you finish the Raptor Mastery quests, but you've got some time for that.
Quests completed: Colonel Kurzen, Panther Mastery 4
Scene 4: The Badlands (level 38)
We may not have been in Stranglethorn real long, but it's probably best we don't hang around too much longer. The southern parts of Stranglethorn are nasty, even at level 38. There are some things we *could* do, but there's also another rather nice zone waiting for us. Don't let the name fool you, but it's called the Badlands.
Oh, by the way. At any point, feel free to fly out to Hillsbrad and finish the water elemental bracer quest at Dalaran. That's one of those "do it when the opportunity strikes you" things, so if you happen to be going to Scarlet Monastery, or in the area for whatever other reason…but do that some time before returning to Stranglethorn for our last crack at it.
So head to Ironforge and check out the quests in the Hall of Explorers. At the very least, you want to pick up Ironband Wants You! There are a couple others that are for Uldaman. We'll discuss Uldaman a little further down, but you're welcome to grab the quests if you've got the space. Also, make sure you grab your letter from Thousand Needles to talk to Martek the Exiled. You *might* also consider buying a Gyrochronatron, Patterned Bronze Bracers, and a Frost Oil from the auction house, as they are used in quests in Badlands, however the cost probably does not justify the reward. You'll be spending around 3.5 gold for the completion of three quests. If you're loaded, though, go for it.
From there, fly (or walk) to Thelsamar in Loch Modan. Talk to the alchemist in the dug-out next to the inn for a quest. The unfortunate part about Badlands is the lack of a quest hub or even an inn or flight point, but we won't be here long so don't worry about your hearthstone. (Just remember to run back to Thelsamar if you want to stop.)
Run across the Loch to Ironband's Expedition and talk to the honcho there. He'll tell you a tale of a missing dwarf somewhere in Badlands. With Find Agmond, as well as Badlands Reagent Run, we are ready to begin. Here's your map:

We're going to do *almost* everything there is to do in Badlands, in one big grand sweep.
As you enter the zone, you will pass the Maker's Terrace, encounter tons of wildlife, and then another Dark Iron excavation site, the Hammertoe Digsite. Go around the digsite and up the hill behind it to find Prospector Ryedol and Sigmund Ironhew. They both have a quest for you. From there, circle around the hill some more to Camp Kosh. Somewhere inside Camp Kosh is a crate for you to loot for Ironhew's quest.
Then finish the circle back to the Hammertoe Digsite and kill your way around til you get Ryedol's Lucky Pick. While you are in the Hammertoe Digsite, make sure to clear the area along the back ridge. Underneath a canopy is a table with a map on the ground next to it. It's easy to miss. But this map is clickable, and will give you another quest. Hit this up first.
Afterwards, return to the two dwarves around the back of the hill to turn in. You'll get two follow-ups, one of which is in Uldaman. Take them both, just the same. Then head southwest into the Valley of Fangs to look for Martek the Exiled and Rigglefuzz for new quests. I don't recommend grabbing Pearl Diving, but you can if you like. Martek's quest is a follow-up to Thousand Needles, one we've been toting for a long time. Note also that there is a vendor here, about the only one in the zone, so make good use of him, but don't sell your buzzard wings!
Continue through the valley and go northwest to Lotwil Veriatus. He has two quests for you, one of which is the Frost Oil quest. So if you've got it, great. If not, drop it. Just behind Lotwil is a ridge filled with Lesser Rock Elementals for his quest. So run up and down the ridges fighting them. There are more powerful ones way in the back; leave those for now. The drop rate on the elementals is awful, and some classes have trouble fighting them, but once you finish, you'll be sent to kill the normal Rock Elementals. This actually goes by quite quickly. Come back to him a third time and he'll send you off for other elementals that are much tougher. Not now.
Return to the vendor in Valley of Fangs. Head a little east, and then turn south. Just before the troggs, you should see a battered dwarven skeleton. Check that for the remains of Agmond. This will give you a second quest for the troggs here. Kill them for indurium and until you can bring down Murdaloc. You'll spend longer collecting the Indurium.
At this point, you're in the clean-up phase. Go south from the troggs to grab Theldurin the Lost's quest Solution to Doom, and then run around collecting the remainder of the pieces you need for Badlands Reagent Run and Scrounging before heading back to the Valley of Fangs, then the two dwarves on the hill, and finally Loch Modan. Scrap Metal for Scrounging will drop from any ogre in the zone, so go to Camp Kosh if you just want to get it done and over with. Note that Prospector Ryedol's follow-up to it will not be available just yet. We're going to eventually want that quest, but not yet, so no big deal.
Head back into Loch Modan, revisit Ironband's Excavation Site and the alchemist in Thelsamar.
Quests completed: A Dwarf and His Tools, A Sign of Hope, Mirages, Martek the Exiled, Coolant Heads Will Prevail (maybe), Study of the Elementals: Rock 1-2, Find Agmond, Indurium, Murdaloc, Badlands Reagent Run, Scrounging
Scene 5: Power to 40 (level 39)
You need to get to level 40. Level 39 will be painful for just about anything we do at this point, since there are very few quests designed for this level range, and we've done all the ones we care about. (The rest are ends of chains or isolated quests.) So to be quite honest, if you aren't level 40 yet, you're probably pretty darn close.
Do what it takes to get there. Here are a few options:
1. Grind. I'm not normally a big grinding advocate, but if you're very close, this might be your best bet.
2. Instances. Scarlet Monastery is your best bet, but Razorfen Downs could also be a possibility.
3. Arathi Highlands has a few scattered quests you might look into at this level. In particular, there is an area off the southwest coast behind Stromgarde with a pirate cove that has some quests. The Princess Trapped series might also give you some things to do.
4. In Dustwallow, there is a quest from the cook at the inn to kill turtles. The turtles are all up and down the beaches to the north, and are fairly decent exp.
5. There are a couple loose quests in Swamp of Sorrows, from the soldier along the south roar and from the Broken at the Harborage in the North.
Also, don't forget to kill Colonel Kurzen and Bhag'thera, and to turn in the quest at Dalaran. If you haven't done those yet, they may help get you there.
And once you are level 40, go train. Here's the part that is harder for some people than others: affording your mount. There are many different ways people afford the 90 gold it takes for their mount. Some make money off their tradeskills. Some buy low and sell high at the auction house. Some simply grind it out. Chances are, if you haven't been trying to make money, you're little more than breaking even.
I will be honest: you do not need a mount. There are times when it is extremely handy for getting from A to B, and in the upcoming series of zones that are vastly spread out, you will definitely want one. But you do not need one immediately. A mount is a privilege…a privilege you will want to have for the upcoming zones, but a privilege nonetheless. In other words, purchase it as soon as you are able to.
We now return you to your regularly scheduled questing.
Scene 6: Splitting Skulls (level 40)
Head back down to Booty Bay again. We have a few more trips we want to clear out before moving on.
Follow the road out of BB past the arena, and then pull off to the east after you pass the Thrashtail Basilisks. There is a goblin strip mine in this area, and while it is not an easy place to handle with the countless adds, Venture Co Mining is a quest that ought to be dealt with now. Skip it if you can't stand it.
From there, cross the road to the west. Behind all the Cold Eye Basilisks, you will find the final set of raptors. Kill 10, and come straight back across the road to the east.
The Ziata'Jal ruins, as well as the other ruins to the north and east, house the Skullsplitter tribe of trolls. You need to kill them for their tusks, and you want to track down mystics for fetish drops. Do not go into the troll city to the east, and be EXTREMELY CAREFUL to watch out for patrols. There aren't many, but they are three-man teams, and will hose you quick. You will have to kill quite a few trolls to get all the tusks.
Once you have 18 tusks and 4 fetishes, go all the way back north to the hunter camp and turn in the Raptor Mastery quest, up to the rebel camp for Troll Witchery, and then hearth back down to Booty Bay.
Quests completed: Raptor Mastery 3, Skullsplitter Tusks, Troll Witchery
Scene 7: Gorillas in the Mist (level 40/41)
Walk out of Booty Bay again. Follow the road for only a very short time, and you will see Elder Mistvale Gorillas to the right side of the road, possibly even attacked by one. Walk around in this general area until you get 5 giblets.
Optional: get a couple friends, and hang out here until you have 9 Gorilla Fangs between you. Witch Doctor Unbagwa will help you complete Stranglethorn Fever, a quest that became available at level 40 in Booty Bay. The quest consists of killing several waves of gorilla attacks ending with one that has Mokk the Savage in it. This is not an easy quest even for a group of 3.
After you have your giblets, walk back toward Booty Bay and stop at the tunnel. If you've ever left Booty Bay in the wrong direction and turned left, you will have run headlong into a Bloodsail Mage that promptly lit you up. Your curiosity will finally be sated. Turn toward this valley and march your way in. Be very mindful of wanderers, and of the *extremely* large aggro and assist radius here. You want to kill nearly all of the Bloodsail pirates in the cove before the bridge.
Notably, there is a fellow here named "Pretty Boy" Duncan. You have a quest called "Pretty Boy" Duncan. You do the math. However, on a crate on the left side of the camp is also a parchment that you will want to pick up for The Bloodsail Buccaneers quest.
Walk back to Booty Bay. (Swim if you want to, you're certainly close enough.)
Quests completed: Scaring Shaky, Return to Mackinley, The Bloodsail Buccaneers 1-2
Moving out (level 41)
Time to amscray, unless you want to fight a bunch of level 44 targets and pirates that will light you up into oblivion. Find the quests Tran'rek and Stoley's Debt from the top of the inn and from Mackinley, and then fly up to Badlands to clean up those Uldaman quests to kick off Act 10.