Note: In this walkthrough, unless otherwise indicated, information such as "left", "west" and so on are based on your actual position on the map. However, if it is written "on YOUR right", it means the right side of the screen relative to your line of sight.
Link wanders with his horse Epona in a dark forest. Two small fairies fly around him and make him fall to the ground. This is when a strange imp with a big mask appears. He gets closer to Link unconscious and takes his ocarina. When Link gets back on his feet, the imp jumps on the horse and runs away.
After your encounter with Skull Kid, get in the trunk entrance, jump from stump to stump, get in the next trunk entrance and fall down! After the cutscene you will turn into a Deku scrub. Skull Kid leaves and one of the fairies gets left behind. After she asks you to help her find her brother, go through the door, move on, then Tatl and you make a deal. Step on the flower, dive and glide towards the door in front of you. Open the door and glide slightly on the left until you reach a chest containing Deku nuts. Pick them up, then glide again to the left and go on.
You will find yourself locked in a new place. Climb the stairs, have a look at the Sheikah Stone if you wish, then when you're close to the door, you meet with the Mask salesman. The man says that an imp stole one of his masks and that he knows a way to return you to your former self. If you can get back your ocarina and the mask stolen by Skull Kid, he will help you. Open the next door and the daily countdown will begin...
You will start in the Southern District. Tatl says you should look for the Great Fairy who should know where Skull Kid may be. Head towards the Northern District which is behind the Clock Tower from where you got out. If you already possess five rupees, you can buy a Clock Town map sold by Tingle. There are bushes in the surroundings that give rupees when cut. (If you don't buy it now, come back later, Tingle will still be here, but will be flying around using his red balloon).
After this, go to the Fairy Fountain in the left part of North Clock Town and walk in the pond. One of the stray fairies is lost. If it is still daytime, go back to Southern District, walk up the runway in the south-east corner leading to the Clock Tower's Laundry Pool and pick up the stray fairy floating over the water. If night has already fallen down, head towards Eastern District, look for the stray fairy up in the sky and use the Deku flower lying around to get her. Bring back the stray fairy to the Fairy Fountain so the Great Fairy of Magic appears. She will give you Magic Power, which means for now: being able to shoot bubbles. The Great Fairy tells you about a man living in an observatory who may help you.
Exit the fountain and get closer to the kid aiming at the balloon. Shoot a bubble to destroy the floating balloon, which will make Jim angry. Talk to him and he tells you about a hideout that leads to the observatory. Then he calls his four Bombers friends and asks you to play hide and seek with them (you will have to find him too) and that before the next morning.
N64: Two kids are in the Northern District, another one is the Western District near the shops and the other two are in the Eastern District, one of them being on a roof accessible thanks to the Deku Flower.
3DS: One kid is in the Northern District, another one is in the Western District, one kid is in the Southern District inside a crate in the centre of the area, another one is in the Laundry Pool inside a crate and the last one is in the Eastern District, on a roof accessible thanks to the Deku Flower. Afterwards, they will give you a five digits code. Write it down and look for a kid in the Eastern District who is near the top right corner. Give him the code, then go ahead. Bounce on the water between platforms, steer clear of the Skulltula, pop the balloon and climb the ladder to enter the Astral Observatory.
Go up the stairs and get on the platform where the Astronomer is. Talk to him, take a look in his telescope and look for Skull Kid on top of the Clock Tower. Then open the door in this room and pick up the Moon's Tear. Go back to the city, go to the Southern District and look for a Deku flower. A Business scrub will be on his way. Trade the Moon's Tear for his Town Title Deed. Afterwards, use the flower and fly towards the Piece of Heart which is on the Clock Tower balcony. If you still have time before the third day midnight, you can go on discovering the city (hereafter).
Midnight ringing, enter the Clock Tower through the balcony, you will meet Skull Kid again. As soon as possible, look up and shot bubbles at him so he will drop the Ocarina of Time that you can now pick up. Suddenly a flashback will start, in which Zelda teaches you the Song of Time. Play the Song of Time once again and you will be back at the dawn of the first day.
Go back to the Mask Salesman in Clock Tower. Talk to him and he will teach you the Song of Healing. Play it to return to normal while receiving the Deku Mask. The salesman tells you about the Majora's Mask and the evil power inside it which could cause a lot of damage!
3DS: After promising to find the mask, he lets you have a Bombers' Notebook!
Exit the tower, go behind it and look at the Owl Statue, which allows you to save your game.
N64: But don't save yet! Go back to East Clock Town and as Link, talk to the kid in front of the passage leading to the Astral Observatory. Get in the passage and back out. At this time, the boy hands you the Bombers' Notebook.