Note that this guide is ancient. Cataclysm changed many of the quests and details.
We'll leave this page up for posterity sake. If you like you can check out our leveling home page, with links to the appropriate class guides and a bunch of leveling tips. Those pages will be updated regularly, into Mists of Pandaria and beyond.
Click here if you want to get leveled faster
Level 1-6 Starting Area: Night Elf
Pick up "The Balance of Nature" and "The Woodland Protector" finish them both to hit level 2 and pick up the second part of the woodland protector and finish that. Get the second part of The Balance of Nature and "A Good Friend" finish the balance of nature then A Good Friend.
You should be around level 4 by now, do "A Friend in Need" and "Ivveron's Antidote" then "Webwood Venom." Do "Webwood Egg" and grind on your way back to the Quest NPC. Pick up Tenaron's Summons and finish that along with "Crown of the Earth" part 1 and 2 picking up Dolanaar Delivery before leaving the starting area.
Level 6-11 Starting Area: Night Elf
Kill all the birds you see, in order to get the "small eggs." You will
cook these up later, or you can sell them on the Auction House. Keep
all the "small spider legs" you find, as well, for the same reason.
Pick up first aid from a NPC in dolanaar if you're a non-healing class such as a rogue or a warrior. Pick up the quest Denalan's Earth then head down to the lake south of Dolanaar to find denalan. Get the quests Timberling Seeds and Timberling Sprouts from Denalan and finish those both up.
Get to Dolonar and talk to Zarrin, the cook, and get your cooking skill
(you'll want the buffing foods eventually.) Talk to Nyoma, the cooking
supplies elf, and buy 50 flour and 50 mild spices. Cook these up. When
that's done you'll cook up your Small Eggs. These give +2 stam. If you
have 7 small spider legs you can trade them in for a recipe and spider
You should be seven now or almost, if you're not grind a bit till you hit 7. Pick up Zenn's Bidding from the Satyr a bit west and off the road from Dolanaar, then get A Troubling Breeze, Gnarlpine Corruption, and The Road to Darnassus. Finish all of those to hit 8.
Pick up Seek Redemption!, and Crown of the Earth from Dolanaar then get Rellian Greenspyre from Denalan. Also up the road right outside of darnassus find the moonwell and get the quest from the NPC up there. Finish The Enchanted Glade, then the quest you get after turning in "Rellian Greenspyre."
While heading anywhere finish up the Seek Redemption! quest and turn that in. Also make sure you do the Crown of the Earth quest. You should be level 9 by now and go back to Dolanaar to pick up The Relics of Awakening. While doing that quest get The Sleeping Druid from a NPC inside the cave.
Do the 4th part of Crown of the Earth and you should be about level 10. Get Oakenscowl from Denalan, and Ursal the Mauler from Dolanaar. Also finish the 5th part of Crown of the Earth along with any other quests you have left to hit level 11.
Level 11-14 Darkshore
Finish up The Crown of the Earth questline in Darnassus while on your way to Darkshore. Get the Bashal'Aran quest and head north from Auberdine up the road to find the ruins. In the blue glowing circle area a NPC will give you the second quest for the area. Finish that quest and head down to the ruins south of Auberdine.
Complete the rest of the Bashal'Aran quest line and do the Tools of the Highborne quest in the southern ruins. While your down there finish the How Big a Threat? quest. Also make sure to pick up the quest from the Night Elf sentinel on the road nearby the ruins.
You should be closing in on 13 now if not grind a bit. When your 13 do the Washed Ashore quests and then the second part of How Big a Threat? Also make sure to pick up the quest from the guard in town requiring you to investigate a red crystal east of town. Finish both parts of that and then the Plagued Lands Quest.
By now you should be 14, if not finish whatever quests around your level in auberdine then get ready for a long run. The Night Elf area simply is not a good leveling area for 15+ or so.
Head to the human lands.
Level 14-16 Westfall
Head to Sentinel Hill and get the Red Leather Bandnas quest along with The Peoples Miltia and Patrolling Westfall. complete all of these to hit level 15. I grinded to 16 at the mine where you completed the first defias quests.
Your going to head to Redridge/Lakeshire now until 17.
Level 16-17 Redridge/Lakeshire
Do the first part of The Defias Brotherhood quest here, pick up the quest from the guard patrolling near the crossroads on your way to Lakeshire. Do the Hillary's Necklace quest along with A Free Lunch, Messenger to Stormwind, The Lost Tools, and Assessing the Threat.
When your done with all of those quests you will be 17 and ready to head back to Westfall and finish that up. Before heading back finish up the Defias Brotherhood quest line for a nice amount of XP.
Level 17-18 Westfall
Complete the messenger to westfall quest from the mayor of Lakeshire. Finish the Peoples Militia quest line and then head to the bottom left of westfall and you will find a lighthouse there. Pick up and finish all three of the quests the NPC there gives you and you should be 18. If you still need some XP grind the Defias Highwaymen for the rest.
Level 18-20 Redridge
You will want to get the Redridge Ghoulash quest, the Everstill bridge, and Blackrock Menace. You will complete these quests in a mixture of grinding/questing to space each quest out a bit. Also get Selling Fish and An Unwelcome Guest for level 19. Grind 3-6k XP then complete one quest then grind a bit more then do another quest.
After finishing these quests and with the grinding you should be near 20, if not already 20. Grind up to 20 and finish. Take An Unwelcome Guest if you can quickly find 2-4 people to help, otherwise skip it.
The other leveing guides on this site are:
If you actually want to level fast, far faster than from this page or any other guide, check out Zygor's Automated in-game leveling guide.