What race are you?
The one for Night elves is just down the road from Darnassus or in Darnassus itself up by the leather worker trainer.
Dorfs/gnomes on the North side of the Great Forge there is leather shop with a trainer downstairs.
Don't know about humans, best best for any of them, ask a guard in the respective towns and he will flag it on your mini map.