Au terme d'Ocarina of Time, Link renvoie Ganondorf dans le Royaume Sacré. La Princesse Zelda redonne à Link sa jeunesse et la paix règne à nouveau à Hyrule. C'est trois mois plus tard que débute l'histoire du Masque de Majora.

Un jour, alors que Link explore les bois, deux petites fées surgissent effrayant Epona. Link se retrouve à terre inconscient. C'est alors qu'un étrange petit bonhomme, Skull Kid, s'empare de la précieuse Ocarina et s'enfuit avec Epona par un passage mystérieux. Bien sûr, Link le poursuit et se retrouve dans un monde totalement bizarre et inconnu : Termina. Il se rend vite compte que la fin de ce monde est proche, car la lune se rapproche dangeureusement. Avec l'aide de Taya, une des fées abandonnée par Skull Kid, Link décide de sauver Termina avant les 72 heures qui lui restent.

D'abord, il devra s'habituer à sa nouvelle apparence et aux capacités qui l'accompagnent. Il devra également faire connaissance avec les habitants de Bourg-Clocher, certains lui étant étrangement familiers. Un grand nombre d'aventures et de quêtes attendent Link dans la mission confiée par le Vendeur de Masques pour déjouer les plans de Skull Kid : rapporter le Masque de Majora.