Majora's Mask begins several months after Ocarina of Time. Link seeks his fairy, Navi, who departed after the events of the previous game. During his search, he is ambushed by a Skull Kid wearing a mysterious mask and his two fairy companions, the siblings Tatl and Tael. They steal both his horse, Epona, and the Ocarina of Time. Link pursues them and falls into a trap; Skull Kid curses Link, transforming him into a Deku Scrub, but inadvertently leaves Tatl behind. With no other choice, Tatl guides Link to Clock Town to reunite with her brother. They meet the Happy Mask Salesman, who pressures Link into recovering the mask that Skull Kid stole, promising to break the curse if he succeeds. After three days, Link manages to locate Skull Kid and retrieve the Ocarina of Time but fails to get the mask. As the moon nears impact, Tael instructs Link to awaken the Four Giants, the guardian deities of the regions in each cardinal direction. Link plays the Song of Time and miraculously returns to the day he first set foot in Termina.

Mistakenly believing that Link recovered the mask, the Happy Mask Salesman breaks Link's curse. He soon discovers that Link failed and flies into a rage. He explains that Skull Kid's mask is Majora's Mask, which contains a powerful evil that can bring about the end of the world. After he collects himself, the salesman dispatches Link to retrieve the mask once more. Link embarks on his quest by going to the four regions that Tael mentioned where he finds that they are afflicted by Majora's magic. In Woodfall, the swamp is poisoned and the Deku princess was kidnapped. Snowhead has been suffering an eternal winter, driving the Gorons to starvation. Great Bay's waters have been contaminated, turning its creatures into monsters. In Ikana Canyon, inhabitants are terrorized by a plague that brings the dead back to life. Through his travels, Link learns that Skull Kid cursed the land as revenge for feeling abandoned by his Giant friends when they became Termina's guardians. Tatl and Tael befriended the lonely Skull Kid and accompanied him in the mischief that led to his theft of the mask, which has been corrupting him ever since. Under the mask's influence, Skull Kid forced the moon on a collision course with Termina.

Across numerous time loops, Link liberates the Giants and summons them on the eve of the Carnival. They manage to halt the moon's descent but Majora's Mask comes alive and possesses the moon itself, abandoning Skull Kid. Link confronts Majora's Mask inside the moon and defeats it. Link, the fairies, and the Giants all make amends with Skull Kid, while the Happy Mask Salesman recovers the now powerless Majora's Mask. The Carnival of Time begins with celebrations based on Link's accomplishments. In a nearby forest, Skull Kid draws himself with Link and his friends on a tree stump.