During the events of Zelda 3: The Return of Ganon, the King of Hyrule had received disturbing news from Tersistas, that Link's ancestor had committed an atrocity on a place named Koholint Island. A whale told him to kill everyone off, so he did it without a thought. How he survived being left adrift in the ocean is still a mystery, but after the defeat of Tersistas, the King ruled it a genocide, and Link, bearing the disgrace of his ancestor, was forced into exile.

However, the king also told Link that since he had saved Hyrule, he'd have a chance to redeem himself. The Nightmares who tried to stop his ancestor had somehow survived, and were trying to stop another island from being exterminated by the Windfish's awakening. If Link can kill it while preserving the island, his exile will end. But to find a way to do so, he must align himself with the Nightmares. Unfortunately, the Wind Fish has a few more defenses this time, and the Nightmare have been captured and are on the verge of being executed. Can he save them all in time, end the Windfish, and save EtwE Island?