La historia comienza cuando se narra la pasada aventura en el Wind waker, como un pequeño niño buscando a su hermana se embarca en una gran aventura, comenzando un día cuando los piratas llegan a la isla donde Link habita, quien diría que se convertiría en el héroe de los vientos.

También que la pequeña pirata "Tetra" que tanto daba lata a Link sería la persona por la que recorre la sangre de la realeza, siendo ella Zelda, o también que su amigo el rey de los leones sería el rey de Hyrule, todo ocasionado por el regreso de Ganondorf para bobrar venganza por un pasado remoto (ocarina of time).

Luego de esto, nuestro héroe de los vientos y la embarcación de piratas buscan un nuevo lugar para empezar un reino, pero de repente aparece un barco fantasma, entonces Tetra decide ir a ver, pero resulta secuestrada, y Link al tratar de ayudarla se pierde en el gran océano. Pero no todo acaba aquí, ya que con la ayuda de la nueva hada acompañante "Ciela" podrás encontrar a Tetra.