The story starts out in the Trophy World's Mid-air stadium, where Mario and Kirby are dueling each other. After the duel, the winner (either Mario or Kirby), freed the loser from his frozen state. Suddenly, a strange alien-like race, supspace army, and the Ancient Minister (the apparent leader) launched out Petey Pirahna who kidnapped both Princess Peach and Princess Zelda in cages. Mario and Kirby start attacking, but only rescue one of the princess. Both princess can be interchanged in the storyline.
After the battle, the Ancient Minister sends out two R.O.B.s who activate a subspace bomb, which sucks up the entire stadium. Mario is sent by Bullet Bill into the distance, and Kirby escapes with one of the princesses. Kirby and the princess land on the Halberd.