O texto a seguir contém spoilers do início ao final do jogo.

Tudo começou em algum momento após os acontecimentos de Ocarina of Time, em uma jornada pessoal de Link a procura de uma querida amizade (implicitamente, a fada Navi). No meio da floresta, aparecem duas fadas que assustam a égua de Link, Epona, fazendo-o cair para trás. Um Skull Kid mascarado aparece e vai até o corpo inconsciente do herói. Revirando Link, começa a vasculhar seus bolsos até achar a Ocarina do Tempo e começar a tocá-la. Link acorda e, num súbito momento de fúria, tenta agarrar o pivete.

Rápido, ele pula e aparece em cima da Epona, porém o herói salta na perna da égua e seguem até um lugar misterioso onde o herói do tempo acaba por se soltar. Indo por dentro daquele tronco gigante, segue rumo a um local que termina em um abismo escuro.

Ao fundo, o jovem herói cai em uma flor rosa e vê Skull Kid junto com as duas fadas.

Com o poder de sua máscara, ele transforma Link em um pequeno Deku Scrub e vai embora. A porta por onde ele passou se fecha e a fada amarela (Tatl) fica para trás, o que a obriga a unir-se com o Deku-Link. Eles abrem o portão e seguem para um lugar estranho. Chegando lá, eles entram em um tipo de uma torre de relógio e encontram o enigmático Happy Mask Salesman (Vendedor de máscaras).

Ele fala sobre as máscaras e que precisa da sua ajuda para resgatar uma que é de suma importância para sua coleção: a que foi roubada por Skull Kid. Em troca, ele promete curar Link da maldição e restaurar sua forma original. Mas, sendo um homem ocupado, o vendedor precisa ir embora dentro de três dias.

Link agora precisará explorar Clock Town (Cidade Relógio), para realizar sua missão. Nesse tempo, ficamos sabendo que a lua está caindo e que deverá se chocar com a cidade também em três dias.

À meia-noite do dia final, vê-se a Torre do Relógio se modificar e abrir uma porta para seu topo. Lá estão Skull Kid e a outra fada (Tael), que menciona algo sobre trazer alguém de quatro localidades (pântano, montanhas, oceano e cânion). Com o poder da máscara, a lua começa a cair mais rapidamente. Deku-Link, sem alternativa, ataca Skull Kid e o faz derrubar a Ocarina do Tempo.

Em um flashback, ele lembra a canção que Zelda o ensinou ao confiar-lhe o instrumento: a Song of Time (Canção do Tempo). Misteriosamente, com forma de Deku a Ocarina se transforma em uma espécie de gaita de foles, e ao tocar a Canção do Tempo, tudo retorna ao momento em que Link pôs os pés na cidade pela primeira vez.

De volta então ao Amanhecer do Primeiro Dia, Link retorna ao vendedor de máscaras, que lhe ensina a Song of Healing (Canção de Cura), fazendo-o voltar a ser um hylian e transformando aquela forma de Deku em uma máscara. Esta pode ser usada e retirada sempre que se queira para se alternar entre formas.

Ao perceber que Link não recuperou a máscara que ele precisava, o vendedor explica: trata-se da Máscara de Majora, um artefato muito poderoso e maléfico criado por uma tribo antiga. O poder da máscara é tão grande que em mãos erradas poderia destruir o mundo. Portanto, novamente Link aceita a missão de encontrar uma forma de recuperar a máscara e evitar a queda da lua. Para isso, terá que buscar os quatro lugares mencionados por Tael.

O primeiro deles é o Southern Swamp (Pântano do Sul) e seu Woodfall (Bosque Catarata). Lá, descobre os problemas vividos entre o povo Deku: a Princesa Deku foi sequestrada e um macaco foi acusado do rapto. Link acaba por invadir o palácio e ajudar o pobre primata. Na prisão ao lado do rei, ele ensina a Deku-Link a canção que ele vai precisar para entrar no templo e resgatar a princesa.

Após conseguir completar o templo local, ele descobre que teria que despertar os 4 gigantes para que segurem a lua e fazer com que toda a Termina se salve. A maldição das águas envenenadas que assolava Woodfall some e o primeiro gigante, que estava aprisionado dentro do monstro Odolwa, desperta, ensinando a canção Oath to Order (Ode à Ordem) e dizendo: “chame-nos”. Em seguida Link encontra a princesa, explica-lhe a situação e a leva de volta ao rei. O macaco é solto, o rei se desculpa pelo seu equívoco e o herói parte para a segunda localização: o Snowhead (Pico Nevado).

Na Vila dos Gorons nas montanhas, Link encontra as Lentes da Verdade. Com ela, enxerga o fantasma de um Goron e o segue até seu túmulo. Ele é Darmani, um herói em sua tribo. Falando sobre seu fracasso em salvar sua terra, ele aceita ser levado pela Canção de Cura e é transformado na Máscara Goron.

Em sua nova forma, Link encontra o Ancião Goron, que o confunde com Darmani, pedindo para que toque uma canção para seu filho, que não consegue dormir. No entanto, ele esquece parte da música, mas tocando esse trecho para o tal filho, o próprio ensina a Goron-Link a versão completa, que logo o faz pregar no sono. Com essa música, consegue-se fazer adormecer o Biggoron que estava bloqueando o caminho para o Templo do Pico Nevado e continuar a jornada. Ao conquistar o templo com a derrota do monstro Goht e a liberação do segundo gigante, a primavera retorna às montanhas e os Gorons ficam livres do frio eterno.

Em Great Bay (Grande Baia), a penúltima localização indicada por Tael, o herói se depara com um Zora desmaiado na água. Sem mais nada poder fazer, Link o leva de volta à margem. Ele diz seu nome, Mikau, e que ele é guitarrista de uma banda que há de se apresentar no Carnival of Time (Festejos do Tempo). No entanto, a vocalista da banda, Lulu, perdeu sua voz depois de ter posto seus ovos, e eles ainda foram roubados pelas Piratas Gerudos.

Mikau tentara resgatá-los, mas não obteve êxito e foi mortalmente ferido. Não conseguindo mais resistir, em seus últimos suspiros, Link toca a Canção de Cura e faz seu espírito se prender à Máscara Zora.

Depois de enterrá-lo, Link parte para o Zora Hall (Salão Zora) e conversa com toda a banda passando-se por Mikau. Entendendo melhor a situação, o herói acaba entrando na Fortaleza das Piratas e resgata quatro dos sete ovos roubados. Os outros três são recuperados em uma estranha formação de terra chamada Pinnacle Rock, infestada de Deep Python, serpentes marinhas gigantes.

Levando todos os ovos ao Marine Research Lab (Laboratório de Pesquisa Marinha), eles eclodem, e os girinos que surgem parecem notas musicais e formam uma partitura, a partir da qual Link aprende a New Wave Bossanova (Bossa Nova das Ondas). Essa canção é capaz de restaurar a voz de Lulu. Tocando-a, o Herói do Tempo restaura a voz da Zora e atrai uma tartaruga gigante, que o leva ao Great Bay Temple (Templo da Grande Baia). Passando pelo calabouço, Link derrota o enorme peixe Gyorg, despertando o terceiro gigante.

Seguindo a leste de Clock Town para a última localização, o Cânion Ikana, Link vai até um cemitério local. Lá ele enfrenta o Skull Keeta, um Stalchild gigante, e obtém o Captains’s Hat, uma espécie de máscara que o fará se passar pelo próprio Keeta. Com isso, ele pode enganar os subordinados e acessar locais abaixo dos túmulos, onde descobre a história dos Irmãos Compositores: Sharp foi ludibriado e vendeu sua alma e de seu irmão Flat ao demônio. Link aprende de Flat a Song of Storms (Canção da Tempestade), a qual ele compôs para aliviar a alma de seu irmão e dar-lhe seu perdão.

Ao finalmente chegar em Ikana, Link acaba por encontrar Sharp, e usa a Song of Storms para curar seu tormento, que tão grande era a ponto de não surtir efeito com o uso da Canção de Cura. Liberando-o da maldição, a nascente do riacho de Ikana, que estava seca, volta a jorrar. A água corrente é força motriz dos mecanismos de uma estranha casa localizada no meio daquele local desolado. Uma casa de aparência alegre e colorida, com um enorme megafone em seu topo. A música alegre que ele emite afugenta os Gibdos, múmias que perambulam pelo Vale de Ikana, a terra dos mortos.
Com esse episódio, Link consegue entrar na casa e salvar o pai da pequena Pamela, que foi amaldiçoado e transformado em um Gibdo. Com as informações ali obtida (e fazendo proveito da Máscara de Gibdo obtida, a qual permite comunicação com as múmias), o herói segue seu caminho até a sala do trono do Castelo Antigo de Ikana, onde enfrenta o rei morto Igos e seus subordinados.

Provando seu valor em batalha e demonstrando suas intenções, Link convence o rei de que ele será de ajuda para seu reino caído, e assim o monarca ensina a misteriosa canção Elegia ao Vazio, capaz de materializar um soldado sem alma, uma estátua à imagem de cada forma que Link pode assumir. Com o uso de seus “soldados”, Link torna-se capaz de subir a Stone Tower (Torre de Pedra) e alcançar o templo localizado em seu topo.

Com os quatro templos concluídos, novamente em Clock Town à meia-noite do dia final, Link chama os quatro gigantes, que seguram a lua e a fazem parar. Jazendo inconsciente, Skull Kid, que até então agiu como um mero fantoche, é descartado pela Máscara de Majora, que intensifica a força de queda da lua (causando mais esforço para os gigantes) e adentra o corpo celeste. Sem pensar duas vezes, Link segue o inimigo.

O cenário que se segue é bem surreal: um campo aberto e uma grande árvore central. Pelo campo, brincam crianças usando máscaras dos chefes dos templos derrotados por Link. Sentada isolada debaixo da árvore, uma criança usando a Máscara de Majora.

As crianças fazem estranhos questionamentos sobre valores de amizade, e por fim a criança sentada chama o herói para “brincar”, dando início à batalha final e revelando formas humanoides bizarras assumidas pela máscara.

Vitorioso, Link sai da misteriosa lua que, enfim, se distancia da terra e desaparece com um rastro de arco-íris. Skull Kid se desculpa, a Majora’s Mask retorna ao vendedor de máscaras e Link pode retornar para sua casa. Se é que ele realmente retornou…