The Palace of Shadow is what lies behind The Thousand Year Door and is the final level in Paper Mario: The Thousand-Year Door. To enter, one needs all seven Crystal Stars. The palace was the home of the Shadow Queen. The Four Heroes locked her spirit in the palace and sealed the exit, the Thousand-Year Door, with the Crystal Stars. The X-Nauts tried to gather the Crystal Stars and unlock the Thousand-Year Door and awaken the Shadow Queen. At the end of the game Mario has collected all seven Crystal Stars and opens the Thousand-Year Door. He goes through the Palace of Shadow and going through all of its obstacles. The palace contains many rooms including an outside garden with Riddle Tower.
There is also the Shadow Queen's throne room and the room where her spirit was kept.