Online:Storm on the Horizon

Quick Walkthrough
# Speak with Razum-dar, then talk to Commander Karinith and Ealcil.
# Complete Cast Adrift and Tears of the Two Moons.
# Find Razum-dar in Mistral.

Detailed Walkthrough
Razum-dar will be waiting for you outside the Ruined Tower you awoke in. He will say that you must become more familiar so your presence won't be suspect. Apparently you fell from the sky, and while before he wasn't sure how you would fit into his mission, he has now decided you may be of help. He will urge you to keep your arrival a secret by claiming to be just another soldier. Then, he will have you speak to Commander Karinith, who will then send you to speak with Ealcil. Karinith needs you to help search for survivors of the storm in the Shattered Shoals area to the west. Ealcil, on the other hand, is a scholar who has just returned from a temple with a mysterious rock that produces endless water. He was attacked by skeletons and barely escaped with his life and the stone, leaving behind the rest of the expedition.

Follow Razum-dar back to the north exit. He will suggest that you to help one or both of them in order to obtain the trust of the locals, then meet him in Mistral, a port city to the north. You will need to complete the two objectives and the quests they lead to (Cast Adrift and Tears of the Two Moons) to complete this quest. Once you have done so, head to Mistral. When you arrive, Razum-dar will be on the north end of the long bridge leading into the city.


Alternate Start
If you leave Khenarthi's Roost before starting this quest, you will be able to acquire it from Captain Tremouille in Vulkhel Guard. He is standing on the deck of the ship you wake up in; you can't miss him. He'll say you slept all the way from Khenarthi's Roost, right through a hurricane. A Khajiit called Razum-dar fished you out of the ocean and paid for your passage, then went to Eagle's Strand, an old fort on the island. If you want to go back to Khenarthi's Roost, he says to find a boatswain called Sugar-Claws. She is on the eastern side of the docks. At first, she'll think that you're there about some worrying business with fish, but she offers to take you to Khenarthi's Roost for free.

Once there, you will be on the shore, facing the south entrance to Eagle's Strand. Head on in, and Razum-dar will approach you.

Notes
If you leave Eagle's Strand before speaking to both Commander Karinith, Ealcil, and meeting Razum-dar at the statues, then you will fail the current objective and be told to find Razum-dar back in the camp. There will be a note from him there, giving you the quest's objectives (Shattered Shoals and Temple of the Mourning Springs) and telling you to meet him in Mistral.
If you complete Cast Adrift or Tears of the Two Moons without starting this quest, Zaeri will appear at those locations once the quest is complete to direct you to the other objective.
If you bypass everything including Eagle's Strand, Shattered Shoals, and the Temple of the Mourning Springs, there is a notice at the Temple of the Crescent Moons and a note outside Silat's House at Windcatcher Plantation entitled To My Friend From the Beach. Engaging in a dialogue with this notice starts the quest.
If you head straight to Mistral, you are able to start The Perils of Diplomacy without completing this quest.
Between the release of One Tamriel and the release of Morrowind, Captain Tremouille was not available as a quest giver, as all Aldmeri Dominion characters started directly on Khenarthi's Roost upon finishing the Soul Shriven in Coldharbour tutorial quest.
Prior to Update 10, you were dropped into Vulkhel Guard upon leaving Coldharbour, and Captain Tremouille was the primary starting point for the quest. During this time, the objectives to complete the quests at Shattered Shoals and the Temple of the Mourning Springs were optional.