ピーチ城ではピーチ姫が、キノコ王国に迫っているクッパ軍団を迎え撃つ準備をしていた。ピーチは強力な兵力を保有するコング族と同盟を結ぶべくジャングル王国に向かおうとするが、そこでキノピオと共に到着したマリオと出会う。マリオから「ダークランドに落ちたルイージを救いたい」と言われたピーチは、訓練用のコースを用意して、これをクリアできたらジャングル王国に同行していいと言う。マリオはピーチからパワーアップアイテムのスーパーキノコを受け取り、能力を高めてコースに挑むが、何回やってもクリアできない。しかし、ルイージを救いたいマリオは何度失敗しても諦めず、コースクリアを目指す。結局マリオは一度もコースをクリアできなかったが、ピーチは諦めずにコースに挑み続けたマリオの心意気を認め、ジャングル王国への同行を認める。
マリオとピーチはジャングル王国で国王のクランキーコングと謁見するが、クランキーは同盟を結ぶのを渋り、闘技場で無敗を誇る息子のドンキーコングを倒せたら同盟を結ぶと条件を付ける。マリオはドンキーとの対決に挑むが、圧倒的な力の差を見せつけられ、一方的に打ちのめされる。さらに、パワーアップアイテムだと思って口にしたマメキノコで小さなマメマリオになってしまい、窮地に陥る。しかし、それでも何度やられても諦めずに立ち向かい、パワーアップアイテムのスーパーベルでネコマリオに変身した事で形勢を逆転し、ドンキーに勝利する。コング族と同盟を結んだマリオ達は、クッパ軍団を迎え撃つため、コング族の兵達と共に空に浮かぶレインボーロードをカートで走り、急いでキノコ王国に戻る。
だが、キノコ王国がコング族と同盟を結んだ事を察知していたクッパ軍団は、レインボーロードを走るマリオ達に奇襲を仕掛ける。数々の攻撃を耐えて反撃するマリオ達であったが、追い込まれたノコノコ大将が自ら突貫しレインボーロードの一部を破壊。その衝撃でマリオとドンキーは海に落ち、そのショックで呆けていたコング族はクッパ軍団に捕らえられてしまう。ピーチはキノピオとキノコ王国に戻り、コング族の兵とマリオを失った事を市民に伝えると共に、王国からの避難を促す。海に落ちたマリオは、溺れそうなドンキーを救うが、突如現れたウツボに吞み込まれてしまう。