Vashj tried several times to kill Tyrande but failed because Tyrande was protected by Elune, the Goddess of Plot Preservation. She got her big break when Azshara became corrupted by the Burning Legion and started the War of the Ancients. Unlike Tyrande, Vashj stuck by her mistress's side, and when Zin-Ashari was dragged under the sea at the end of the war, Vashj was turned into a naga by the OId Gods, along with a ton of other Highborne and Azshara herself. With Azshara, she waited for years under the sea while establishing the city of Nazjatar.
After ten thousand years of waiting, Azshara finally decided that it was time for the world to know about the naga. This was conveniently timed with Illidan Stormrage calling the naga, who he'd known as the Highborne, to come help him in his ongoing quest against
sanity the Lich King. Azshara sent Vashj to meet Illidan on the surface as her envoy. Vashj and her naga allies, noting that Illidan shared their hatred of night elf society, helped Illidan escape from Kalimdor and headed to the Tomb of Sargeras to get a powerful artifact.
Vashj's naga fought off the night elf forces of Maiev Shadowsong as Vashj and Illidan made their way into the Tomb of Sargeras. They recovered the Eye of Sargeras and used it to collapse the Tomb on top of Maiev, who (of course) didn't die. Vashj and the naga headed to Dalaran, where they met up with Illidan. Illidan told them that Maiev was coming back with reinforcements, so Vashj used her naga summoners to try to break apart Northrend and destroy the Lich King's base of power. However, they were interrupted by Malfurion and had to flee to avoid capture. Vashj watched Illidan save Tyrande Whisperwind from certain death and then vanish into a portal, which probably ticked her off a bit. "I thought we had something special! Why did he save that ho-bag and then run away? What does she have that I don't, besides functioning legs and a lack of gills?"
But Vashj was nothing if not loyal to Illidan. Rather than return to serve Azshara, she decided to find some new allies to help her and Illidan in the future. Her gaze wandered to Prince Kael'Thas Sunstrider, leader of the blood elves, who was being forced to do grunt work for the racist Alliance general Garithos. Kael'Thas had been sent on a mission that involved using ships, but was stuck because his shipyard had been destroyed. Vashj and the naga offered to help Kael'Thas and the blood elves cross. Kael'Thas didn't want to accept her assistance, seeing as he had fought alongside Maiev and Malfurion at Dalaran, but he had no other choice. The naga ferried the elves across the river.
Garithos, unhappy with Kael'Thas for accepting the help of the naga, sent him to fight off a large army of undead with only a few troops. Once again, Vashj offered to help the blood elf prince, and again, Kael'Thas had no choice but to accept. They fought off the undead together, but after the battle Garithos came and arrested Kael'Thas for treason. Vashj broke into his dungeon through the sewers, freed him, and told him they could escape to Outlands and join Illidan there. After a quick fight with Garithos's troops, Vashj and Kael'Thas fled through an open portal with their respective forces.
Vashj and Kael'Thas wandered through Outland until they stumbled upon Maiev Shadowsong. Maiev had finally captured Illidan and planned to haul him back to Azeroth in a prison wagon. The duo defeated Maiev and freed Illidan from the prison. He commended them for their loyalty and bravery and told them he planned to defeat the Pit Lord Magtheridon and rule Outland. The naga and blood elves, commanded by Illidan, Vashj and Kael'Thas, managed to beat Magtheridon and take Outland for their own. However, Illidan had forgotten to check out the neighborhood before conquering Outland, and his peaceful reverie was interrupted by the arrival of the Burning Legion. The demon lord Kil'Jaeden appeared and reminded Illidan that he had promised to kill the Lich King and failed, so he had better hop to it unless he wanted to see what his internal organs looked like while he was still alive. Sighing, Illidan, Vashj, and Kael'Thas packed up their armies and headed to Northrend, where they were (again) thwarted. Illidan was defeated and left for dead by Arthas, and Vashj and Kael'Thas dragged him back to Outland.
Where she is now: Vashj is the matron of a vast dynasty of Illidari naga. She rules them from Serpentshrine Cavern, deep under the lakes of Zangarmarsh. Presumably, she's still working for Illidan,although she probably would also like to rejoin Azshara someday. Lady Vashj enjoys sowing discord, crocheting, and killing Nihilum, Curse and Death and Taxes about a hundred times a week.
Identifying characteristics: Vashj is a female naga, with four arms, a tail, and snakes instead of hair. She is a mix of a hunter and a sorceress. While she has formidable magic powers, she prefers to use her bow and her guards to fight off challengers. The top guilds aren't talking about her strategy yet, but it's known that she summons adds and shoots raid members with arrows. Members of Nihilum, whose web site still crashes my computer, have described the encounter as "not impossible but close to it." They've gotten her to around 25 percent.
Why we need to kill her: 1. PHAT LOOTZ, including a rumored 95 DPS dagger. 2. She holds one of the vials from the Well of Eternity that are needed to access the Battle of Mount Hyjal in the Caverns of Time. Prince Kael'Thas holds the other. 3. She and her naga are corrupting the natural ecosystem of Zangarmarsh, and apparently we're supposed to care about mushroom people.
For more information: WoWWiki on Vashj, Vashj on Worldofwarcraft.com, Nihilum discussing the Vashj encounter, Death and Taxes not discussing the Vashj encounter, the last thing you see before you die to Lady Vashj.