とても平和な国、キノコ王国。そこでは魔王クッパ伯爵により、 破壊と略奪が繰り返されていました。(て、矛盾?) そんなある日、婚期を逃したクッパ伯爵は人間の中から 自分の嫁としてふさわしい女性を探します。 そこに目をつけられたのが、他ならぬキノコ国第一王女、ピーチでした。 クッパ伯爵は腹心カメックにピーチ姫をさらうように命じます。 そのころ、同じくピーチ姫を狙っていたマリオも 姫を守るべく、キノコ王国を目指して旅立ちますが…