I leveled mainly with questing. Did everything in Howling Fjord, Borean Tundra, Dragonblight, I then did half the quests in Grizzly Hills, then moved to Scholazar Basin.


The Basin rocks, seriously.

After that I was close to 79 and quested in Storm Peaks (mainly the rescue goblin -> Transform into blue girl questline -> work for the elementals quests.)