The Altar of Shadows is the prison of Teron Gorefiend. It is located in the central southern edge of the Shadowmoon Valley, opposite Netherwing Ledge. You can see it on the map as a small altar icon directly south of the Scryers' Sanctum of the Stars base where the green falls go off the edge. Coordinates are
[58, 71].
This altar is required for making the tailoring item, Shadowcloth. Unlike Spellcloth, creating Shadowcloth does not cause a creature to spawn.