The story begins with Mario heading to Peach's Castle, but on the way there, Bowser stops him, Mario prepares to fight him, but before he does, Bowser explains that there is a situation going on at his castle. Mario, intrigued, asks Bowser what this situation is, and Bowser proceeds to explain that Fawful and Smithy, two of their arch-rivals, have teamed up to build the dreaded robotic hybrid named Smawful, who has Peach kidnapped. Mario, shocked at the news, makes a suggestion: He and Bowser must now join forces against a common foe. To save the kingdom from total annihilation, Bowser explains to Mario that what Smithy and Fawful are after is the Beanstar, and there are five pieces scattered throughout the kingdom. Mario suggests combining his Mario Kart with Bowser's Koopa Kruiser to get the pieces before Smithy and Fawful. Bowser agrees to this and they go to Toad's Construction Shop. Unfortunately, they do not find Toad, but they find Midbus, Fawful's former henchman, who explains that Fawful turned against him and allied with Smithy. Midbus wants to know how strong Mario and Bowser are as a team and challenges them to a tutorial battle. After the battle, he combines Mario's Kart with the Koopa Kruiser to form the Kruiser Kart. Then, they go off in search of the five Beanstar pieces.
Once there, they spot the Axem Rangers, who hold the first Beanstar piece. They challenge Mario and Bowser to an air battle for the piece. Mario and Bowser prevail against Blade, their ship, and it falls into Bowser Volcano. They grab the first piece and head to Seaside Town to get the next star piece, guarded by Yaridovich. Along the way, they spot Johnny Jones, who explains that he is the owner of the item shop. Then he sends Mario and Bowser on their way equipped with new items.
The heroes meet up with Yaridovich, who challenges them to a fight, which they win. They head to the Forest Maze in search of Bowyer and Mack, who hold the next two star pieces. The heroes defeat the pair of cronies.
The last Beanstar piece is in the hands of Fawful and Smithy. But before Mario and Bowser can claim it, they are confronted by Smawful, Fawful and Smithy's hybrid bodyguard. The heroes engage it in battle, and emerge victorious. Smawful calls his masters before exploding. Fawful and Smithy say they won't give up the Beanstar pieces that easily, and engage our heroic duo in combat. After a lengthy final battle, the heroes overwhelm the two antagonists, and they reclaim the last Beanstar piece and rescue the princess. They return home to a victory celebration hosted by Toad. Mario and Bowser state that their truce is now permanent. The story ends with Mario and Bowser being presented Hero Medals for their efforts.