In the beginning of the film, Princess Peach interrupts Mario's video game session by jumping out of the television and requests Mario to protect her. Mario agrees, but Bowser succeeds in kidnapping her. Mario and Luigi almost dismiss it as a dream, but Mario finds an emerald necklace from Princess Peach. Working at the grocery store, Luigi notices Mario holding the pendant and then, identifying the gem from a book he has read, believes it can guide them to Mushroom Kingdom where they can get rich. Mario tries to call the author of the book, and he answers, already knowing his name. A dog-like creature, Kidibango, however, steals the necklace. Mario and Luigi chase the dog and enter a warp pipe, where they find Kinoko Sennin, the author of the book. He tells them that Mushroom Kingdom is being attacked and Princess Peach believed from a prophecy that Mario and Luigi can save it, but Bowser has taken her because she has rejected his proposal to marry her. Mario, angry and motivated, wants to rescue Peach and her kingdom, so Kinoko Sennin advises they get help from the mushroom, flower and star, scattered in the kingdom. Luigi becomes encouraged by the coins he may find along the way, so he joins Mario along with Kibidango.
On their adventure, two Goombas watch their progress and try to impede them. The first time, they tell a famished Luigi that they are mushrooms and lead him a field of mushrooms that cause erratic effects to him, such as laughing and crying. Mario struggles to get Luigi to normal, but a Paratroopa interferes and tries feeding him to her chicks. Mario finds a mushroom in a block of ice and tries to climb to reach it, but reveals a rock that shoots coins, surprising him and causing him to fall, but he lands safely. Luigi then finds out that the coins have transformed to mushroom people. One, calling himself Toad, explains that Bowser has transformed them to coins and thanks Mario and Luigi for rescuing them. They give Mario and Luigi a key item, a Super Mushroom, and let Mario, Luigi, and Kibidango continue on their way. Mario uses this Mushroom to help fend off enemies, such as Koopa Troopas and Bullet Bills along the way.
Mario and Luigi meet these two Goombas again, and the Goombas lead them to a field infested with Piranha Plants. They narrowly escape, but anger a Lakitu in the process for disturbing its flowers. Lakitu throws Spiny Eggs at Mario and Luigi, though Mario and Luigi taunt at it for missing. Lakitu then summons rain to cause these eggs to morph into Spinies. It also causes a beanstalk to grow and trick Lakitu for a moment to think Mario is defeated, but Mario grabs some of the cloud before Lakitu realizes and escapes. Mario eventually saves Luigi and Kibidango when he triggers the cloud to snow and make the Piranha Plants and Spinies hibernate. This cloud then transforms into another Toad, who thanks and gives Mario a Fire Flower. This flower helps Mario defeat more enemies with fire, including Buzzy Beetles.
After resting and eating, Luigi leads Mario and Kibidango into a cave, but they are immediately locked in. Mario sees the two Goombas and begs for forgiveness, but the Goombas refuse and consider their mission to stop Mario, Luigi, and Kibidango successful. They leave a Hammer Bro. to guard the prison cell. While waiting in the cell, Mario gets a daydream of dancing with Peach, but Luigi has found a way to escape. Mario, however, is still in his daydream and wounds up kissing the Hammer Bro.. The three then quickly leave. When they escape, Luigi realizes that these coins are fake and tosses them into the water while also accidentally tossing a star into there. Realizing the mistake, Mario and Kibidango swim to try to get it while avoiding many fish including Cheep Cheeps. They grab the star, which is hidden in a clam, but retreat in a sunken ship for safety. They steer this ship out of the water, and they reunite with Luigi. Riding the ship, Mario, Luigi, and Kibidango have the three items and are prepared to face Bowser crash his wedding ceremony.
They are spotted when Peach notices them approaching the castle. Mario and Kibidango enter the area through a hole in the wall and see Bowser. They then chase him while Luigi searches for treasure. Mario and Kibidango arrive at a lava pit, and the two Goombas, with a control panel, challenge Mario to jump across elevator platforms. Meanwhile, however, Luigi finds a leak and floods the room with water. While Mario is saved, this causes the castle to collapse. Among the remains, Mario sees Bowser grab Peach and is ready to fight Mario. Kibidango reminds Mario to use the power-ups. Mario does use the Super Mushroom and the Fire Flower, but Mario is distracted by more food, and Bowser manages to damage and throw him. Peach begs Bowser for forgiveness and is even willing to marry him as long as Mario is spared. Bowser hesitates, but wants to destroy Mario since Mario has yet to use the Super Star. Bowser tries to squish Mario and Luigi, but Mario uses his star and manages to fight and defeat Bowser.
At the end, the castle is restored to Peach's castle and the landscape becomes lush. Princess Peach thanks Mario, and Mario returns Peach's pendant. Peach talks about another half of the pendant, which Mario promises to find. Kibidango, however, transforms into Prince Haru of Flower-koku. He is the keeper of the other half and is about to marry Peach, but Bowser has cursed him into his dog form. This devastates Mario, but Princess Peach thanks him and Mario and Luigi promise Princess Peach help whenever she needs it. At the end of the movie, Bowser and the Koopa Troop are shown working as employees for Mario and Luigi's grocery store.