Le Palais des Ténèbres se trouve à la place du Palais de l'Est. En arrivant dans une zone de labyrinthe, vous devriez apercevoir le dessin d'une flèche au sol. Suivez les 2 flèches du sol ainsi que le chemin qui part sur la droite. Tout au bout du chemin, continuez tout droit (vous passerez dans le buisson) et montez. Ensuite, repassez dans le buisson vers la droite et descendez un peu pour rentrer complètement dans le buisson.

Dans ce labyrinthe caché, essayez de marcher un peu n'importe où. Normalement, vous devez ressortir à droite du buisson en compagnie d'un singe bleu. Si ce n'est pas le cas, foncez dans les murs avec les Bottes. Suivez le chemin jusqu'à l'entrée du Palais et le singe vous proposera de vous ouvrir le Palais à condition de lui donner 100 Rubis. Acceptez et il ne vous reste plus qu'à entrer dans le Palais des Ténèbres.