The Palace of Darkness is the first of the seven Dark World dungeons where the Seven Maidens are being held prisoner. It is the dark world equivalent of the Eastern Palace in the Light World.
The Palace of Darkness is located in the eastern part of the Dark World. The only way in is to pay a monkey named Kiki one hundred ten rupees to open the door.
Link is trying to free the seven maidens in order to defeat Ganon. The Palace of Darkness is, according to Sahasrahla, the prison of the first maiden.
The boss is the Helmasaur King. He lives in a room surrounded by spikes, so must have thick skin. He wears a helmet which is vulnerable to the Magical Hammer, underneath which is his weak point, a giant green gem.