With so many sources of information out there about the Naga I’ll try and cover what I assume is the true canonical history of the Naga. We’ll start off as usual with a little RP for some flavor and see how things go. Again any feedback is always helpful.
If anyone wants to know anything about the Naga from the RPG books, which may not be considered canon, I would be happy to post something about that part of the story as well in the future. This may include such topics as current culture, appearance, gender, etc…
But for now, enjoy!
Evils in the Depths
A letter from Archivist Richard to her grace, The Honored High Archivist Veda
Grandmaster of the Stormwind Archives
Most Honored High Archivist,
I sent you greetings my lady from the great city of Darnassus. Never in all my years have I felt so at peace then I do in this magnificent place. I was initially skeptical about this assignment to be honest, but now I feel like a child again walking the streets of Stormwind. Being here though reminds me how far humans can be from nature at times.
Back to business however, as you asked I have made contact with the Sisters of Elune and the Cenarion Circle here. I am very excited in a sense for what I have learned particularly from the priestess assigned as my guide during my stay here. I have been here over a week now and I write to you late as learning of the information you asked for has been more difficult than I thought.
The last two days however, have proven very fruitful. I have attached to this letter my report which sadly is not entirely complete as I have a great deal of work still to do, but the priestess aiding me has been most helpful since she was assigned to me yesterday.
I will report again when I have completed more research. I hope to eventually speak with High Priestess Whisperwind soon as well. I have heard she is busy, but I have been promised an audience as soon as possible.
In Light and Knowledge your servant,
Richard
Once when the continent of Kalimdor was whole Night Elf society was centered around the great city of Zin-Azshari named after their queen, Azshara. Within the depths of the city also dwelled the now fabled Well of Eternity, the source of Azeroth’s arcane magic. The coming of the Burning Legion would change the peaceful Night Elf society forever.
The highest echelon of elves become known as the Highborne(Quel’dorei) and believed themselves greater than all others. As these Highborne continued to tap the power contained within the Well of Eternity they called Azeroth to the attention of the Dark Titan Sargeras. The initial invasion of the Legion caused countless casualties among the Kaldorei(Night Elves) save the Highborne of course. The great city Zin-Azshari was reduced to ruins save the queen’s palace. Some did escape the disaster and flee the city. 
In the end Azshara and her Highborne, along with the Burning Legion, were defeated. However, coinciding with this victory was the event known as The Sundering set in motion as Sargeras attempted to enter Azeroth. As the great continent of Kalimdor shattered Queen Azshara and most of her Highborne were sucked beneath the waves as the dying Well of Eternity consumed Zin-Azshari.
Many Thousands of years passed as the world recovered from this disaster. Night Elf society would recover as well after a time. However, several years ago after the battle for Hyjal Summit the Night Elf Illidan Stormrage discovered the presence of Naga deep beneath the waves of Azeroth. A short time later the Night Elves discovered the possible link between the Naga and the Highborne.
Over several years to the present day many skirmishes with the Naga have confirmed Night Elf suppositions that these sea creatures were indeed once elves. Most among the Night Elf scholars believe queen Azshara herself still lives beneath the waves and that her power may exceed that of any living creature on Azeroth even the Dragon Aspects.
(Note: Thanks to a high elf informant in Silvermoon I have confirmed that both Illidan, called The Betrayer by many, as well as the former Prince, Kael’thas Sunstrider, both knew who the Naga were before most. In fact when the Naga joined Illidan’s cause lead by Lady Vashj the High Priestess Tyrande Whisperwind verified that she remembered the name Vashj when she was captured during the War of the Ancients. Linking all of these facts together raises still more questions that I will ponder during my stay in Darnassus) 
Foremost among the Naga on the surface was a powerful witch named Lady Vashj. During the War of the Ancients Vashj served as Queen Azshara’s personal handmaiden. Remembering Illidan from that long ago war Vashj and her legion of Naga pledged loyalty to him. Soon after Vashj convinced Prince Kael’thas of Silvermoon and his people to join Illidan’s cause as well. The Naga on the surface, along with the Blood Elves, went with Vashj to join Illidan in Outland.
In Outland most Naga were gathered in the region called Zangarmarsh, within and around the Coilfang Reservoir. No one was sure what exactly the Naga wanted with the water in the marsh. The only reasonable explanation presented was they simply wanted to control most if not all of Outlands water. Beyond that no one is sure exactly what was going on. However, the Naga were eventually defeated and Lady Vashj and her generals were all killed.
Even with so many Naga defeated included Azshara’s greatest champion many Naga still roam various regions of Azeroth and the threat of Azshara’s return still looms in the eyes of many Night Elves.
