Visions of Vashj'ir Past

Guide to Vashj'ir Shimmering Expanse Alliance quests:

The Vashj'ir quests start in Stormwind with Call of Duty.
The immediate pre-requisite for these quests is Across the great Divide which starts in Kelp'thar Forest .

Initial chain:
The Looming Threat
Backed Into a Corner
Rundown
Silver Tide Hollow

Several side quests are now enabled:
Slippery Threat, Don't be Shellfish, and A Distracting Scent
Also a side-chain:

• 
  
• The Great Sambino
• 
  
• Crabby patrons
• 
  
• Undersea Inflation
• 
  
• Totem Modification
• 
  
• Back in One Piece
• 
  
• Toshe's Vengeance (optinal linking quest)
• 
  

The main chain continues at Toshe Chaosrender
Vortex (optional)
Vengeful Heart
Fathom-Lord Zin'jatar
A Pearl of Wisdom (optional;starts from Luminescent Pearl from the boss)
Nespirah
Making Contact
Slave Labor and Stick it To Them
Capture the Crab
Breaking Through
We Are Not Alone
Body Blows, Hopelessly Gearless, and Still Valuable
Overseer Idra'kess
Waking the Beast (also unlocks A Cold Welcome)
A Powerful Need to Eat
Clamming Up and Art of Attraction plus Odor Coater
Bellies Await
You can do all these simultaneously:

• 
  
• Swift Approach
• 
  
• Caught Off-Guard
• 
  
• A Better Vantage
• 
  
• An Occupation of Time (optional)
• 
  

While killing naga, hope Ancient Elven Etching drops to start Piece of the Past
If you do these quests and haven't already continued on the main chain,
The Call of the Blade will set you back on track.

Main chain continues:
Upon the Scene of Battle [You can actually get this quest a bit earlier]
Visions of the Past: The Invasion of Vashj'ir
Turn to Naga and do:

• 
  
• Reoccupation
• 
  
• The Revered Lady
• 
  
• To the Fathom-Lord's Call and Built to Last
• 
  
• Not Soon Forgotten (ends first vision)
• 
  

Looking Forward
Clear Goals, Not Entirely Unprepared, and Properly Inspired
Swift Action
Fallen but Not Forgotten and Gauging Success
Visions of the Past: The Slaughter of Biel'aran Ridge
As a naga again, complete:

• 
  
• By Her Lady's Word
• 
  
• No Trespass Forgiven and Stolen Property plus Chosen Burden
• 
  
• Setting an Example (optional)
• 
  
• The Culmination of Our Efforts (ends second vision)
• 
  

Losing Ground
Desperate Plan
Come Prepared, Unfurling Plan, and Hostile Waters
Honor and Privilege
Welcome News
Visions of the Past: Rise from the Deep
As a naga, work on

• 
  
• Devout Assembly and Her Lady's Hand
• 
  
• At All Costs
• 
  
• Final Judgement (awards Visions of Vashj'ir Past)
• 
  

If you are missing any of the naga optional quests, you may now talk to Wavespeaker Valoren to get the Blade of the Naz'jar Battlemaiden which allows you to repeat any of the visions

This chain [for this zone] wraps up:
A Breath of Fresh Air (enables The War has Many Fronts link to Deepholm)
Full Circle

The Vashj'ir quests conclude in the Abyssal Depths

What happened to the Battlemaiden?

I was hoping she would show up at the end of the Vashj'ir quests but she never did.

This quest chain didn't seem to take place that long before the player enters Vashj'ir.

There are various quests in the Shimmering Expanse, specifically around the Ruins of Vashj'ir, where you get quests and re-enact certain key points in naga history. There's 3 major points where you do it, hence the 3 visions of Vashj'ir Past.