Attention ; ce qui suit dévoile des éléments importants de l'intrigue.
En allant dans les égouts, ils sont aspirés par un tuyau vert vers un vortex. Ils finissent par être séparés et Mario atterrit dans un endroit avec des champignons énormes : le Royaume Champignon.
Il rencontre Toad, qui lui fait apprend qu'il se trouve au Royaume Champignon et que Luigi, avec des informations qui ont été donnés par Mario, a été arrivé sur le pays noir, qui cherche depuis plusieurs années à conquérir le royaume champignon. Toad conduit Mario alors auprès de Peach, en plein conseil : Bowser a volé la Super étoile qui est possédée par les Pingouins et va essayer d'envahir le royaume avec son pouvoir. Peach accorde de l’aide de Mario, prêt pour sauver Luigi, et le fait tester sur un parcours tout en lui montrant les habitudes que peuvent lui donnet les power-ups comme les champignons rouges. De son autre côté, Luigi est capturé par les soldats du roi Bowser et emmené devant Bowser. Amoureux de la princesse (même s’il la déteste), il agit très mal au fait que un humain, de la même espèce que lui, le fréquente. Il tire la moustache de Luigi ce qu'il sait sur Mario sans beaucoup de difficultés, à cause qu’il est peureux, avant de le jeter.
Mario, Peach et Toad se rendent au royaume des Kong, dans le pour obtenir une armée de singes pour défendre le Royaume. En chemin, Peach montre à Mario qu'elle est aussi arrivée par accident par un tuyau vert dans cet même endroit quand elle était une enfante. Elle a grandi et élevée par les Toads, ils l'ont nommé princesse du royaume Champignon une fois adulte. Arrivés, ils se voient au début opposer une fin de non-recevoir par le roi Cranky Kong mais il accepte finalement à condition que Mario vainc son fils Donkey Kong lors d'un duel. Alors que la situation est en de plus en mal de Mario, il parvient grâce aux power-ups dispersés à prendre le dessus et à battre Donkey Kong.
L'arrivée de Bowser étant rapide, Cranky propose de prendre le raccourci vers la route en arc-en-ciel pour se rendre au château de la princesse Peach à bord de karts. Mais une fois sur la route, ils sont pris bousculés par Bowser, prévenu de leur plan par ses espions Koopas. L'embuscade est une catastrophe : une partie beaucoup de l'armée de Kong est capturée par Bowser, Mario et Donkey Kong tombent de la route et atterrissent dans l'océan et seuls la princesse Peach et Toad réussissent à revenir au château. La princesse demande de évacuer la ville et se prépare à battre Bowser seule. La forteresse volante de Bowser arrive peu après et Bowser demande en mariage et menace de tuer Toad si elle refuse.
Mario et Donkey Kong réussisent à s'échapper du système digestif d'une baleine qui les a avalés et retournent au château avec aux pièces détachées du kart de Donkey Kong. Utilisant les différents power-ups qu'ils trouvent sur leur chemin, ils détruisent l'armée Koopa et arrivent au moment où Bowser allait brûler dans de la lave tout leurs prisonniers. Peach aspire une fleur de glace qui lui permet de congeler Bowser un certain temps et de sauver les prisonniers des Koopas. Luigi est sauvé par Mario alors qu'il allait être brûlé dans la lave : les deux frères se retrouvent. En colère, Bowser envoie un Bill Bourrin géant détruire le château mais Mario le dirige vers un tuyau vert, le faisant exploser dans entre les mondes. Mais l'explosion dans cet endroit a aspiré la forteresse de Bowser et tous ses occupants, qui se trouvent téléportés à Brooklyn, à New York.
Enragé, Bowser bat Mario face à lui. Réussissant à vaincre sa peur, Luigi vient aider à Mario et ils finissent par aspirer la Super étoile. Grâce à l’invincibilité qu'elle leur donne ils arrivent à battre Bowser et son armée, sous les yeux des habitants de New York et de leurs parents. À l'aide d'un champignon bleu, ils rétrécissent Bowser et l'enferment dans un bocal en verre, mettant un terme à sa menace. Acclamés par tout le monde, Mario et Luigi décident d'habiter dans le Royaume Champignon où ils reprennent leur activité normale.