Mario, Luigi, Princess Toadstool and Toad are traveling through outer space onboard a spacecraft known as the Flying Pizza, and are on their way to help a group of Mushroom space colonists. The colonists are in trouble, due to the fact that Darth Koopa is threatening to blow up their planet. However, Mario's group is unaware of the fact that they are being pursued by Darth Koopa's Koop Star.
While Mario pilots the Flying Pizza, Luigi gulps, and tells him to check out his rear-view video screen. Upon doing so, the screen brings up a shot of Koop Star, informing Mario that Darth Koopa's moon-sized spacecraft is on their tail. Mario turns on the ship's "Fasten Seatbelts" light, warning Princess Toadstool and Toad to stop their card game, and to fasten their seatbelts, while he increases the Flying Pizza's speed.
Not wanting Princess Toadstool to escape, Darth Koopa orders Mouser, who is piloting Koop Star, to give chase. Mouser responds by putting Koop Star into overdrive, telling Darth Koopa that not even the Flying Pizza could outrun Koop Star. After telling Mouser to close in on the Flying Pizza and to activate Koop Star's tractor beam, Darth Koopa readies his Stormtroopas to prepare to board the Flying Pizza; telling them to do what they want to Mario, Luigi and Toad, but to take Princess Toadstool prisoner.
Mouser locks onto the Flying Pizza with the tractor beam, and pulls the ship into Koop Star's docking bay. Darth Koopa then orders his Stormtroopas to board the Flying Pizza, while Mario's group prepares for the assault by drawing their Lightplungers. Luigi has trouble activating his Lightplunger, but Princess Toadstool tells him to say the magic words: "May the pasta be with you", and activates it for him.
Soon, the Stormtroopas discover Mario and his friends, and engage in several duels with them. Mario knocks a Stormtroopa aside, while two Super Troopa-sized Stormtroopa's attack Toad, only for their Lightplungers to hit each other. Another Stormtroopa foolishly grabs ahold of Princess Toadstool's Lightplunger, and gets shocked. Princess Toadstool then shocks yet another Stormtroopa that was holding Luigi upside-down, knocking him out. Mario and Toad then toss the final, defeated Stormtroopa into a pile with the rest of his team.
Before Mario's group can celebrate their victory, Darth Koopa boards the Flying Pizza, demanding for them to leave his galaxy. Princess Toadstool and Mario talk back to Darth Koopa to defend their right to stay. Mario redraws his Lightplunger, while Darth Koopa draws his, and challenges him to a duel. Mario and Darth Koopa fight with their Lightplungers, while Mario's friends cheer him on. Eventually, Darth Koopa has Mario up against a wall, however, Mario fights back, and manages to kick Darth Koopa into the far wall. Just when Mario figures that Darth Koopa is at his mercy, the space tyrant pulls out a Freeze Gun, and shoots Mario with it, encasing him in a thick shell of ice. Princess Toadstool demands for Darth Koopa to release Mario, only for Darth Koopa to freeze her as well, along with Luigi and Toad.
Mario's group, still frozen in ice, are brought aboard Koop Star, where Darth Koopa orders Mouser to thaw them out with a Heat Gun. When Mario comes to his senses and reacts to Darth Koopa, Mouser threatens him with his Freeze Gun, forcing him to stay in his spot. Princess Toadstool asks what Darth Koopa wants with them, so Darth Koopa responds by bringing down a monitor, and explains that he needs to destroy the Mushroom Colonists' planet, due to the fact that they won't surrender it to him. Darth Koopa tells Princess Toadstool to order the colonists to give up, or else their planet will be destroyed by his Birdo Ray, and shows a simulation of what will happen to the planet if he uses the aforemented weapon. Princess Toadstool exclaims that the colonists will never give up, so Darth Koopa orders Mouser to activate the Birdo Ray which will go off in thirty minutes, and to have the heroes escorted to the Intergalactic InSinkErator.
After bringing Mario's group to a platform above the Intergalactic InSinkErator, Mouser explains how the industrial-sized garbage disposal will eliminate them through the use of a flow chart, and that their remains will be ejected from Koop Star into space in a Garbage Pod. Mouser then pushes a button, dropping Mario and his friends down into the Intergalactic InSinkErator. While falling, Mario pulls out his plunger and uses it to hang onto the wall, while his friends grab ahold of him, with Luigi dangling right above the Intergalactic InSinkErator's buzzsaws. The thought of garbage disposals reminds Mario of all the ones that he and Luigi used to fix back in Brooklyn, and Luigi remarks that they always had silverware stuck inside of them, pulling out the utensils that he was saving for their next picnic lunch. Mario demands for Luigi to drop the utensils, and Luigi does so, causing them to jam the Intergalactic InSinkErator's buzzsaws, bringing them to a halt, just as Mario's plunger loses its grip on the wall. With the buzzsaws turned off, Mario's group safely falls past them, and continue to fall deeper into the Intergalactic InSinkErator.
Meanwhile, Darth Koopa gloats about how he's going to conquer the Mushroom Colonists' planet, and that eventually, the universe will be known as the "Koopaverse". Mouser returns to Darth Koopa, to inform him that Mario's group has been "disposed" of, and directs him to the Garbage Pod that's supposedly carrying what's left of them down towards the Mushroom Colonists planet. Mario's group, all still in one piece, are riding inside the Garbage Pod, which crashes on the desert surface of the planet, sending them all flying out of the pod upon impact. Luigi lands on a Pokey, greatly angering it.
Mario, Toad and Princess Toadstool have landed upon what appears to be a red rock, and are unsure of what it is, except for the fact that it's hard. Toad kicks the rock, which reveals itself to actually be part of large Cobrat. Mario, Princess Toadstool and Toad flee from the Cobrat, and run into Luigi, who's running from the Pokey. The Cobrat spits a bullet, which ends up hitting the Pokey, blowing it up. Mario comes up with a plan, and tells the others to follow him while he runs in circles around the Cobrat. Watching the group run in circles causes the Cobrat to get coiled up, only for it to uncoil, making itself dizzy. Mario and his friends leap onto the Cobrat's back, and Mario uses his plunger as reins for the Cobrat, which he takes control of, so that they can ride it to the Mushroom Colony. Back onboard Koop Star, Mouser informs Darth Koopa that the Birdo Ray is set to go off in sixteen minutes. Having arrived at the Mushroom Colony, Princess Toadstool explains to her friends and Obi-Wan Toadi that they need to do something to save the planet. Mario requests to have lunch, but Obi-Wan Toadi explains that they don't have time to eat. When Princess Toadstool points out that they can't give up, Obi-Wan Toadi explains that someone needs to penetrate Koop Star in a Mushroom Starfighter, so that they can disable the Birdo Ray. With the promise that he will receive lunch afterwards, Mario agrees to take on the task, and boards a Mushroom Starfigher. Before Mario leaves, Obi-Wan Toadi presents him with a pizza to bolster his spirts, and tells Mario: "May the pasta be with you". Mario then takes off, and after Obi-Wan Toadi gives the signal, Luigi, Princess Toadstool and Toad take off after Mario in their own Mushroom Starfighters.
After flying into space, the Mushroom Starfighters are confronted by Stormtroopa Starfighters, of which they dodge the attacks of. Toad succeeds in blasting a Stormtroopa Starfighter, while Princess Toadstool dodges a Stormtroopa Starfighter attacking from behind, only for it to hit a second Stormtroopa Starfighter. With a path cleared, Mario flies over to Koop Star, and travels through a canyon-sized groove along the surface of the spacecraft. A Stormtroopa Starfighter attacks Mario from the rear, but Mario swerves away from a protuding wall, which the Stormtroopa crashes into. Another Stormtroopa Starfighter attempts to shoot Mario down, but Toad blows it up.
With only ten seconds left on the Birdo Ray's timer, Mario flies into a hole on the surface of the groove, and enters Koop Star. After flying past some pipes, Mario opens the dome of his Mushroom Starfighter, and tosses a Bob-Omb at the foundation of Koop Star, causing it to blow up. As a chain reaction, Koop Star as a whole begins to self-desctruct. Darth Koopa and Mouser board an emergency Space Raft, and get blasted into space once Koop Star blows up entirely. Looking back, Mario laughs as Darth Koopa and Mouser uncontrollably float away on the Space Raft.
Mario's group returns to the Mushroom Colony in their Mushroom Starfighters, where the colonists cheer on their victory. Once Mario exits his Starfighter, Obi-Wan Toadi congratulates him. Mario explains that he couldn't have done it without the pizza he received, or without the help of his friends, and suggests that the pasta was with them. The talk of pasta reminds Mario of lunch, and he asks Obi-Wan Toadi where the lunch he was promised is. Upon hearing this, Mario, his friends and Obi-Wan Toadi all laugh.
Animation and continuity errors