前作と見た目の雰囲気こそあまり変わらないものの、物語の背景やシナリオなどにハードな描写が増え（メインとなる街が荒れ放題なうえシンボルが「絞首台」である、「マフィア」「裏の世界」「例のブツ」などの反社会的な言葉が出てくる、さらに「親の金を盗った」「カードでイカサマした」などの犯罪行為の登場、心理的な恐怖を描いたシナリオが存在するなど）、音楽の雰囲気もかなり堅いものが増えた。この傾向は続編『スーパーペーパーマリオ』でより一層顕著になる。
ストーリー.
遠い昔、あるところにそれはそれはとても栄えた街があった。しかしあるとき、大きな災いが降りかかり一夜にしてその街は地の底へ沈んでしまう。そしてそれから年月がながれ、全てがおとぎ話となった頃、何もなくなったその地に人が集まり新たな街が形成された。
そして、時は流れ、ピーチ姫がキノコ王国を巡る旅をしている途中、ゴロツキタウンに立ち寄っていた。ある時、街の中を散策していたピーチ姫は物売りのおばあさんから綺麗な箱をもらう。すると、手にした箱が突然光りだした。
それからしばらく経ったある日、マリオのもとに手紙が届く。差出人はピーチ姫であった。それにはこのようなことが書かれていた。
「私は今、キノコ王国を巡る旅に出ているのですが、宝の地図を手に入れました。ゴロツキタウンという街で物売りのおばあさんからもらった箱に入っていたのです。私一人じゃ宝探しは大変なので手伝ってください。地図は手紙に入れておいたのでそれを持って、必ず来てください。ゴロツキタウンの港で待っています。」
その手紙を読んでゴロツキタウンの港に来たマリオだったが、ピーチ姫の姿が見当たらない。港で姫を探しているとフランクリ先生を探しているクリボーの女の子、クリスチーヌと出会う。彼女に地図のことを話すと、彼女の恩師である考古学の権威、フランクリ先生から話を聞くことができた。
宝を追っていけばピーチ姫とめぐり会えるだろうと思い、マリオは新たな冒険に出るのであった。
システム.
ゲームの流れ.
バトル.
舞台.