- "This is the royal palace of the Deku Kingdom. This is no place for outsiders."
- — Deku Palace Guard
The only way Link can gain entry into the palace, is to transform into Deku Link. In any other form, the Deku Scrubs at entrance to the palace refuse to allow him to entry. The castle consists of many hallways, the throne room, and a series of gardens. All areas of the palace are patrolled by Deku Palace Guards.
Upon entering the Southern Swamp, Link finds that the swamp water has been poisoned. He travels into the Woods of Mystery, where a monkey approaches him and guides him to Koume, who has been injured by the Skull Kid. Link gives her a bottle of Red Potion concocted by her sister Kotake, and she is restored. Upon exiting the forest, Link encounters more monkeys, who tell Link about their brother, who has been mistakenly arrested for abducting the Deku Princess.
Link travels to the Deku Palace and finds the prison cell where the monkey is imprisoned. The monkey tells Link that the Deku Princess went to Woodfall Temple with the monkey's help, in order to find out what has been making the swamp water poisonous. While in the temple, she was ambushed by Odolwa and imprisoned. The monkey teaches Link the "Sonata of Awakening", a special song, necessary in order to raise Woodfall Temple from the waters of Woodfall. They are discovered, and Link is thrown out of the Deku Palace. Link has no choice but to leave the monkey to be tortured by the Deku King's subjects. Link travels to Woodfall Temple, defeats Odolwa and frees the Deku Princess, clearing the name of the monkey.
Points of interest
Outside of the main palace is an entry area in which disconnected bridges separate the Palace from the rest of the swamp. On both sides of the bridge are Lily Pads. To the right of the castle walls is an area containing a spot of Soft Soil. Link must, at one point, plant a Magic Bean in this patch of soil in order to find his way into the jail cell. To the left of the palace walls, is the entrance to the Deku Shrine, where Link can race against the Deku Butler in order to win the Mask of Scents.
In the lavish throne room can be found the Deku King, the Deku Butler, the royal guards, and the small jail cell where the Imprisoned Monkey is being kept. After Link rescues the Deku Princess, the monkey is released.
Inner Palace Garden
Both the northern and southern gardens are constantly patrolled by Deku guards. If they spot Link, they will kick him out of the palace, whether he is wearing the Deku Mask or not. The southern garden is bigger than the northern, and in the area can be found a Hidden Hole where Link can purchase Magic Beans from the Bean Seller. The northern garden is smaller, and has many Rupees scattered around, as well as a Piece of Heart.
Outer Palace Garden
A small garden to the right of the Deku Palace, this area is where Link must plant the Magic Beans to access the upper floors of the Inner Palace Garden.
After Link defeats Odolwa, he can race the Deku Butler through the Deku Shrine to obtain the Mask of Scents.