Auchindoun is very much hit-or-miss on its lore, in my opinion. Some aspects of it are very cool, and others are quite... lacking. This is one area in which the retcons and alterations that accompanied The Burning Crusade are very apparent. The end result gave a proper 'feel' to the environment, but makes its history a little befuddling.
The city of Auchindoun was founded as a City of the Dead by the Draenei. It was a burial place for their fallen brethren, beginning the remains of D'ore, a Naaru who had been killed in the crash of Oshu'gun. It remained this way for some time, a beautiful(though macabre) mausoleum in the heart of Terokkar Forest, second only to the Shadowmoon Valley of old and its blessed Temple of Karabor in the hearts of the Draenei of Outland.
Unfortunately, all good things must come to an end. During the rise of the First Horde, the Bleeding Hollow Clan of Orcs laid siege to the City of the Dead, much like what happened to the Temple of Karabor(now known as the Black Temple). The Bleeding Hollow turned Auchindoun from holy ground to a fortress. The Bleeding Hollow defiled the grounds of Auchindoun quite thoroughly themselves, and this was only made worse by their ceaseless attacks on the Alliance Expedition which had worked so diligently to force the Orcish Hordes from Azeroth. The expedition, with Turalyon, Alleria Windrunner, Khadgar, Kurdran Wildhammer and Danath Trollbane at the helm, took the fight to the Bleeding Hollow rather than allow themselves to be hassled. The Alliance Expedition took their turn to lay siege to Auchindoun. The Bleeding Hollow did not last long within their fortress.