Once you're back in Nabooru Town after getting the Boots, walk east from Nabooru and walk straight onto the ocean. The Boots enable you to walk on certain parts of the water. If you walk straight east from Nabooru, you will eventually make it to the Ocean Palace. However, before you do that, you should get the Heart Container that is hidden in a screen north of the palace.

To find it, first walk straight east from Nabooru, then when the desert sand is only two blocks to the south, go north. There is a hidden path here that goes to the north. When you go north as far as you can go, head east. You will eventually reach a hidden screen that has a heart container.

Now go back west and then south, then east to get to the Ocean Palace.

Ocean Palace

At the Ocean Palace, the entrance statue does NOT hide a magic jar or Iron Knuckle, so just ignore it and go down the elevator. Head east to a room full of blue Ropes spitting rocks while the wall statue spits blue energy at you.

In the next room, you have to cast the Fairy spell to get up onto the high ledge. To get the key, you have to exit to the right and then come back to this room as normal Link. Once you have the key, exit to the right again.

The next room has a crumbling bridge over lava with a 200 point P-Bag on it and a bunch of statue heads floating at you.

In the next room, there are bricks that you can break or jump over, and there is a red Iron Knuckle, a Bot, a ceiling dripper, and another red Iron Knuckle. Go through the locked door and head down the elevator.

There is nothing good to the right, so go to the left where some orange wizard guys will put flames on the floor. There is also a Bubble here.

The next room is an excellent place to level up. Allow the blocks to make a layer at least six squares tall. Break the bricks such that you can stand three blocks up. Break blocks to the left until the orange Moa comes at you over and over again. If you are at the correct level, you can just keep killing infinite Moas, getting 50 points each time you kill it, and occasionally getting a 200 point P-Bag or a red magic jar. To make it even easier, cast Fire.

When you have leveled up as much as you feel like, break the bricks to climb up to the key. Once you have the key, exit to the left.

Kill the orange Iron Knuckle in here, then jump and hit the wall statue to make a red magic jar pop out. There are a couple more orange Iron Knuckles up ahead, and an orange Moa. Take the elevator down.

There is nothing useful to the right, so go to the left and kill or avoid the orange fire wizards and the Bots.

In the next room, there are Bubbles, a Bot, and ceiling drippers, as well as a 200 point P-Bag. Go down the elevator.

You can go to the left if you wish, but all that you will find there is a 200 point P-Bag beyond a Mace Demon and a Bubble. So go to the right. Use the Jump spell to get to where the red Iron Knuckle is guarding the key. After you get the key, go to the right. There are Bubbles and some fire wizards.

Keep going right and you will find a blue Iron Knuckle and what looks like a dead end, when really there's a secret passage through the wall to the right. The passageway is raised one square up, so jump and go through the wall to the right.

There are fire wizards here, and you eventually reach a room with Bots, drippers, and an elevator. Go past the elevator. The next area has Tinsuits and more fire wizards. Beyond that is another elevator. Go up.

There are blocks that you can break, and three blue Stalfos. Past them, you will find a key. Return to the elevator and go down. Then go to the left until you find the elevator that has drippers on both sides. Go down.

There are floating statue heads here that spit energy at you, and fire wizards. Unlock the door and go to the next room. The statue above the door might give you a red magic jar. There is an orange Iron Knuckle followed by a blue Iron Knuckle. Unlock the door to get the flute. Now go back the way you came, go up the elevator, and go to the left, jumping to get into the hidden passage in the wall.

Keep going left until you reach the elevator. Go up, and unlock the door to the left. There is a Bubble and a Mace Demon here. The statue on the wall will spit out a red magic jar if you hit it.

Soon you will get to an elevator. If you go to the left, you can fight a red Iron Knuckle and avoid a Bubble to get a 200 point P-Bag. Otherwise, at the elevator, go down.

There are Bubbles and fire wizards here. The P-Bag at the top is 50 points. To the left, there is an orange Iron Knuckle, a red Iron Knuckle, and a blue Iron Knuckle. Get the key from the end of the room, then return to the elevator and go up two floors.

Kill the orange Iron Knuckle and unlock the door, then kill the blue Iron Knuckle. After that, kill the red Iron Knuckle. The boss, Gooma, is in the next room.

Gooma

Gooma slowly moves around. When Link gets close, he spins his mace before eventually hitting Link with it. Cast Shield because Gooma is tough. The Jump spell can also be helpful. When Gooma swings the mace toward you, jump over it and then hit Gooma on the lower body. You can also try pushing Gooma toward the right side of the room, because when he's there, he can't use the mace. Then after hitting him, go to the left to make Gooma reappear.

Once you defeat Gooma, get the key, walk to the right to put the crystal in place, then exit to the right to get out of the palace. Your next destination is New Kasuto.