Professions skills are split between expansions now, you'll have a separate skill bar for each expansion. This guide is for the "Vanilla" Herbalism skill in the current retail version of World of Warcraft. I have a separate guide for Classic World of Warcraft, so if you are looking for that, visit my Classic WoW Herbalism Leveling Guide.
Table of contents:
First, visit any trainer in the main cities of old Azeroth - just ask a guard, and learn Herbalism. (Orgrimmar, Stormwind, etc.)
The amount of herb you'll get is determined by your skill level. But this means it's still recommended to level in zones where your skill level is close to the herb's hidden skill requirement. You will get much fewer herbs if you start picking the highest level herbs with herbalism skill 1.
If you have the [Sky Golem] mount, you should use it while leveling herbalism because you can pick herbs without dismounting.
1 - 70
For the first 70 points, you can go to any starter zone, there is not much difference between them. You can also just skip to the next part in the guide if you have a higher level character.
Playing WoW Classic?
Visit my Classic WoW Herbalism leveling guide 1-300 if you are looking for the Classic WoW guide. Profession skills are split between expansions in the latest World of Warcraft expansion, you'll have a separate skill bar for each expansion, and you can level them separately. This guide is for the "Vanilla" Herbalism skill in Shadowlands.
70 - 115
Hillsbrad Foothills is a horde only zone, this means it might be a bit harder to reach it for alliance players, and for low level players I recommend Darkshore.
There is just so much herb in this zone. You can find Frozen Herbs at the top of Alterac Mountains, and they can contain Mageroyal, Briarthorn or Bruiseweed.
115 - 185
There is no Goldthorn at Western Plaguelands, go to Feralas if you want to farm it.
185 - 255
You will gather the following herb: [Sungrass]
In both of the zones below the most common herb will be [Sungrass]. I recommend Thousand Needles because there are a lot of [Khadgar's Whisker] in Eastern Plaguelands and they will be green for the last few points. I also like the easy layout of Thousand Needles, you just go in a straight line and you can't miss the herbs.
Go to Eastern Plaguelands if you don't have a flying mount.
255 - 300
You will gather the following herbs:
Swamp of Sorrows
The whole zone is filled with herbs. You can find them everywhere.