This game is about Princess Peach (Princess of the Mushroom Kingdom) who finds a map in an old town that is filled with crime. She mails the map she finds to Mario with a letter. Luigi reads it to Mario. He then sets off to this town called Rogueport. Mario then has to find the Crystal Stars (powerful star shaped stones; when all seven are collected the Thousand Year Door opens). There is a door deep in the sewers of Rogueport (the Thousand-Year Door) which will open if all the crystal stars are collected. It is said that a demon's spirit rests behind the door. The X-Nauts (a group of robot-like people that are trying to collect the crystal stars in order to awaken a demon to destroy the world) try to steal the crystal stars in order to awaken the evil demon and wipe out the planet so that they can become dictators of the world.
The last boss of the game is the Shadow Queen who possesses (takes over) Princess Peach.
Three shadows (The Shadow Sirens) are somehow related to the demon.