The story begins on a clear night in the Mushroom Kingdom where fireworks are seen shooting up throughout the night sky. It is the night of the big Mushroom Carnival and many people from far and wide are there including Toad, Toadette, and Yoshi. Mario runs up, exhusted and out of breath, but he is still able to greet his friends. Princess Peach appears on the stage and informs all of the carnival patrons that a very special guest from a very advanced city has arrived to preform for the concert. The preformer is none other than the famous popstar and F-Zero racer, Kate Alen! As Kate begins to preform with her beautiful pipes, she stops and begins screaming. Everyone ponders the reason of Kate's screaming until they look up into the sky and see none other than the undisputed lord of evil, Black Shadow! Black Shadow is on a giant futruistic gunship, and commands the ship to procede firing lasers at the people below. Panicked, all of the carnival guests run away and duck for cover. (Stage 1: Defeat 20 Enemies) (Playable Characters: Mario, Toad/Toadette, and Yoshi) Mario, Toad/Toadette, and Yoshi are the only ones still standing, and they proceed to fight off the army of Death Soilders from Black Shadow's Dark Million Organization, however once they are finished destroying the soilders, they realize that both Kate Alen and Princess Peach are nowhere to be found, let along the Gunship piloted by Black Shadow. The foursome decide to run off and look for the kidnapped women, and proceed to run off towards a trail of pink fire that hangs in the air.