After you go through Parapa Desert, you reach Parapa Palace.
Enter the Palace
At the entrance to Parapa Palace, just go to the right until you reach an elevator. Get into the elevator and press down to go down. You can also press up in any elevator to go up.
Once you reach the lower floor, go to the left. There will be enemies called Tinsuits bouncing around, but they are very easy to defeat. Just jab them with your sword.
Continue to the left and there will be some Bots on the bricks. They will bounce around and move toward you. Keep your distance if a Bot is just sitting there quivering, because it means that it might be about to jump straight at you. Otherwise, just jab these with your sword until they die.
Continuing to the left, a Red Stalfos will attack. To hurt it, you have to crouch and stab it with your sword. If you try hitting it while you are standing up, you will just hit its shield. However, be careful, because in order to block its sword with your shield, you need to be standing up. Try not to stab the Stalfos when it is about to stab you with the sword.
After you kill the Stalfos, hit the key with your sword to take it.
Now head back the way you came and go past the elevator. You will eventually reach a locked door. Just walk up to it to use your key and unlock it. Keep going to the right.
There is a Bubble in the next room. It flickers and has a skull in the center. Try to avoid it, because it steals your experience points and magic if hits you. Don't bother trying to kill it, because it has so many hit points that even if you were at level 8 attack, it would still take a while to kill it. But you can stun it and render it harmless for a moment if you hit it with your sword. However, it's better to just avoid it entirely if you can.
In the next room, there is a Red Stalfos. Kill it the way that you did before. In the next room there is an elevator. However, you should go past it because you will need a key down there and you don't have one yet.
Instead, continue past the elevator. You will encounter another Red Stalfos. Once you get past it, the next room has a Bubble, another Red Stalfos, and a Bot.
Soon you will reach yet another elevator. If you go past it, you will reach a room with a fairy. If you want to, you can jump up so that you touch the fairy (make a running start.) This will refill your life. HOWEVER, the fairy will disappear after that and it will not reappear until you get a Game Over or you save your game. You might want to leave it alone for now.
Back at the elevator (the one just before the fairy,) go up the elevator. You will encounter more Tinsuits. There is also a key at the end of this room. Keep going to the right and you will reach a room with a Bot and more Tinsuits.
After that, there is a room with a big red monster who throws maces at you. He is exactly like Hammer Bros. from Super Mario Bros. (In fact, I have to wonder if they used the game code from Super Mario Bros. when they were making this game.) Anyway, to defeat this guy, you need to wait for a gap in the maces that he throws. Then when you can safely go through, just start stabbing the monster until he dies, being careful to avoid him when he walks forward and backward.
With the red monster gone, you can get the key. You can hit the statue behind the key to make it drop a red jar, which will refill your magic.
Return to the elevator and go down ONE floor (not two.) Go to the left and you will be back in the series of rooms where you fought some Red Stalfos. Eventually you will reach the elevator that you passed before.
Go down this elevator and head to the left. You will reach a room with a bunch of Bubbles floating around. If you can get a Bubble off of the screen, it can't go back toward you, although if you return to that spot, the Bubble will still be there and will start bouncing around again. Avoid the Bubbles carefully and continue left.
Kill the Bots that jump down from the steps, and then go up onto the bridge. This bridge crumbles under your feet, so run to the left without stopping. There is a P-Bag on the bridge that you can get if you very quickly stab it and then continue running. But if you don't want to take the risk, you can just run past, and the P-Bag will still be there the next time you go to that room. Be sure to avoid the Bots after the bridge.
In the next room, there is a mace demon throwing maces at you. Go past the maces when there is a big enough gap, then stab the demon to death.
After that, you will encounter an orange Iron Knuckle. It can move its shield up and down, so if you try to stab its unprotected part, it might move its shield and block you. Be sure to watch to see where it is going to swing its sword. It can swing the sword high up or down low. You can see which one it will be when it holds the sword behind its head before it swings. This will give you a small amount of time in which to crouch or stand up to block the hit.
If you have trouble hitting it, you can try to jump toward it and hit it on the way down, and then quickly run away from it and repeat.
And remember, if you find that this is way too difficult, you should go to the overworld and level up with some random enemies near a town, healing up as needed during the process, and then come back to the palace once you have leveled up.
Once you have killed the Iron Knuckle, unlock the door behind it and step onto the green platform to pick up the Candle. This item will illuminate dark caves. You will need it in order to continue to the next palace.
In fact, you can leave Parapa Palace now and continue toward the next palace if you feel like it. Some players skip the palace bosses until closer to the end of the game. They just get the treasure from the palace and then leave. But if you don't want to do that, then continue reading.
Go back the way that you came until you reach the elevator. Ride it up to the next floor. Then go to the right until you reach the other elevator. If you didn't take the fairy in the room past the elevator, you can do so now.
Ride the elevator down to the lower floor. You will find an orange Iron Knuckle, so defeat it as before. Then there are a couple of Red Stalfos.
In the next room there is a Mace Demon. Unlock the door and continue on. Yet another Iron Knuckle is waiting for you.
In the next room, there are some curtains and columns. When you reach the center of the room, a life meter will appear on the left side of the screen, and you will be faced with a monster known as Horsehead.
Before the battle begins, you might want to cast the Shield spell if you have enough magic for it.
To defeat Horsehead, you will need to jump toward it and hit the top of its head. The rest of its body is protected with armor, so be sure to hit the upper part of its head. Horsehead will swing a mace at you, so be careful when jumping toward it. That's pretty much all you need to know about fighting Horsehead.
When Horsehead is defeated, a key will fall from the ceiling. Catch it, then go to the right and unlock the door. Jump onto the platform and walk toward the right. One of Link's six crystals will automatically float to the top of the statue. Then Link's experience points will automatically increase until you level up. Choose an attribute to level up, or just choose cancel if you want to save up your points so that you can level up a different attribute.
Now you can walk through the exit on the right and you will leave the palace. Now it's time to make your way to Ruto Town.