『マリオストーリー』（MARIO STORY、欧米版タイトル『Paper Mario』）は、任天堂より2000年8月11日発売のアクションRPGである。また、開発はインテリジェントシステムズが行っている。ペーパーマリオシリーズの第1作目であり、マリオRPGシリーズの第2作目である。

概要 
1996年にスーパーファミコン用ソフトとして発表された『スーパーマリオRPG』の続編として製作されたタイトル。のちにペーパーマリオシリーズとして展開されることとなるシリーズの第1作目である。

発売はNINTENDO64後期であるが、開発自体はNINTEDO64初期から進められており、開発段階では64DD用ディスクソフト『スーパーマリオRPG2』として発売が予定されていた。しかし、開発初期に発表されて以降、実際の発売近くに『マリオストーリー』と改題して再び発表されるまでは大きな開きがあり、当初の発表時とは画面構成が大きく変化している。

絵柄は絵本のような雰囲気のもので、登場キャラは紙のようにペラペラになっている。

音楽は辻横由佳が担当、原曲アレンジを近藤浩治が担当した。

バーチャルコンソール版は2011年8月時点で、『みんなのニンテンドーチャンネル』内の「みんなのおすすめ」でブロンズランク（おすすめ度80-85%）を獲得している。

2021年12月10日より『NINTENDO 64 Nintendo Switch Online』の収録ソフトのひとつとして配信開始。

ストーリー

オープニング 
星達の煌く夜空の彼方にある「星の国」には、星の精という人々の願いを叶えることを仕事とする者がいた。星達の力の源であり、願いを叶える力を持った宝物「スターの杖」があった。

杖は宮殿に収められ、7人の星の精達によって大切に守られてきた。しかしある日、クッパとカメックババが宮殿に現れ、スターの杖を奪い取り、杖の力で星の精達をカードに閉じ込めてしまった。星の子が宮殿に駆け付けたときは、杖も星の精も奪われた後だった。

そんな大事件が起きているとは知らないマリオとルイージの元に、ピーチ姫からのパーティの招待状が届いた。マリオとルイージはキノコタウンへ行き、姫の待つキノコ城へ入った。

キノコ城に着いたマリオは城の奥にいたピーチ姫と会話するが、キノコ城が地面の下に隠されていたクッパ城によって天空に持ち上げられてしまう。キノコ城が天空に浮いている事に驚くマリオとピーチ姫の前にクッパが現れる。

クッパの目的はキノコ城ごとピーチ姫を誘拐することだった。奪ったスターの杖でパワーアップしたクッパはマリオをやっつけてしまい、クッパに敗北したマリオは天空に上がったキノコ城から地上に落とされてしまった。

プロローグおよびステージ1～8 
地上に落とされたマリオはクリボー一家に助けられる。一家の長男であるクリオが仲間に加わる。

キノコタウンの北部にある星の降る丘を訪れたマリオとクリオは、7人の星の精から状況を伝えられ、冒険に出ることを決意する。

その後、ステージ1～7のそれぞれで7人の星の精を1人ずつ助け出していき、ステージ8では天空に浮かぶクッパ城に乗り込み、ピーチを救い、星の国を救うことになる。

システム

ゲームの流れ 
マリオを操作して、物語の舞台であるキノコワールドのあちこちを冒険し、閉じ込められた7人の星の精を助け出していく。

今作では明確なステージ分けが存在しており、初めにマリオが星の精に関する情報を何らかの方法で聞き出し、その居場所へ向かい始めた時点でステージが始まる。そして星の精を守っているボスを倒し、星の精を救出するとステージクリアとなる。

ステージクリア後はキノコ城に捕らえられたピーチ姫を操作するシーンが入る。このときはピーチ姫を操作（一部例外あり）して、部屋をこっそり抜け出してキノコ城内を探索、次に助け出す星の精に関する情報を集める。7人の星の精をすべて救出するまでこの流れを繰り返し、最後はピーチ姫とスターの杖を取り戻すためクッパ城へ向かう。

フィールド上 
3Dの背景の中に一定の大きさの土台が浮かんでおり、上に飛び出す絵本の様な構造物が置いてあるという独特のフィールド構成をしている。フィールド間は細い道で繋がれており、ドガボン以外の敵はここを通って追ってくることはできない。

マリオ達キャラクターは紙の様にペラペラに表現されており、土管に入るときは少し丸くなって回転しながら入ったり、高い所から落ちるとひらひらと減速したりと、演出も紙の様なものが多い。また、建物に入ると壁や天井が開いて中が簡単に見られるようになるが、これは画面手前からの固定方向視点を維持するためでもある。

フィールドにはマリオ作品らしく穴や段差などの仕掛けが多数あり、マリオや仲間の能力を多用しないと解けない。中には初めて訪れた時点では解けない仕掛けもあり、一度クリアした場所に、レベルアップしたり新たなアイテムを手に入れたりした後で訪れなければならないこともある。

『スーパーマリオRPG』はコマンド入力式RPGだったが、本作の開発者はマリオらしくアクション性を持ったゲームにしようと考えた。また『ゼルダの伝説』のような謎解き要素を入れたいと思い、マリオシリーズの特徴的な敵キャラクターをゼルダの伝説のアイテムに置き換えることでゲームとして成立させられると考えた。序盤に仲間になるカメキやピンキーはゼルダの伝説のブーメランと爆弾と同じ機能を持っている。

戦闘 
前作の『スーパーマリオRPG』同様シンボルエンカウント方式であり、フィールド上の敵と接触するとバトルになる。その際、接触した敵が必ず戦闘画面における最前列となる。

本作では「先制攻撃」の概念が追加されている。敵に接触する代わりに何らかの攻撃を加えた場合は先制攻撃が成功した扱いになり、マリオが戦闘開始直後に一度攻撃を与えたり、敵に何らかの状態異常にしたりできる。逆に敵に攻撃されて戦闘に入ると「先制攻撃を受けた」という形になり、マリオが戦闘開始直後一度攻撃を受ける。先制攻撃では基本的にそのキャラとマリオとの間でダメージの増減が行われる。また、一部のキャラは最前列に出ると普段とは違う行動をする。

勝負はターン制で、味方全員の行動→敵全員の行動で1ターン。「行動」には原則的に逃げる（失敗したときのみ）、アイテム使用、仲間の交代も含まれる（先制攻撃で始まった場合、そのキャラが一回分多く行動することになる）。

今作におけるマリオの攻撃手段は基本的にジャンプとハンマーのみであり、新たに加えられた以下の特徴がある。
 天井にいる敵にはジャンプ攻撃ができない。また、原則として頭に棘をつけている敵・炎に包まれている敵にジャンプ攻撃をしようとすると、ダメージを与えられず逆にマリオがダメージを受ける（先制攻撃も同様）。電気を帯びている状態の敵に対してジャンプ攻撃をすると、その敵にダメージを与えられるがマリオもダメージを受ける（このタイプの敵への先制攻撃は存在しない）。
 ハンマー攻撃は地上の最前列にいる敵にしかできない（複数の敵が最前列にいるとみなされる場合もある）。ただし、先制攻撃は空中の敵に対しても可能である。前方にトゲなどを構えた敵に対してハンマー攻撃をしようとすると、ダメージを与えられず逆にマリオがダメージを受ける。
後述する「バッジ」の中には、ジャンプ時のトゲや炎によるダメージをなくしたり、より強力なジャンプやハンマー攻撃ができるようになったりするものもある。なお、敵キャラによってはマリオたちから受けた攻撃や自身の特定の攻撃により、位置が空中から地上、あるいは天井から空中や地上に移るものがいる。

また、ハンマーやジャンプには、それぞれハンマーには「スーパーハンマー」、「ウルトラハンマー」、ジャンプには「スーパーブーツ」、「ウルトラブーツ」とグレードアップさせられるアイテムが登場し、入手することで攻撃力アップのほか、通常のハンマーでは壊せないブロックを壊せるようになったり、通常のジャンプでは探索やアイテム入手が出来なかったものが出来るようになったりと、フィールド上での行動範囲を広げられるようになっている。

マリオが攻撃する際や敵の攻撃を受ける際の「アクションコマンド」が前作より引き継がれている。これは、攻撃や防御の際に特定の操作をすることによりその効果を高められるというものである。前作ではゲーム開始直後から使用できたが、今作ではティンクからアイテムの「ラッキースター」をもらわないと使用できない。他のマリオRPG作品では最初からアクションコマンドが使用できるが、途中からアクションコマンドが使用可能になるマリオRPG作品は本作のみである。

戦闘は通常戦闘と強制戦闘の2種類があり、前者は戦闘中逃げられる。後者は発生場所が決まっており、逃げられず、先制攻撃もない。無敵時のドガボン以外のボス戦は全て後者に属する。

マリオや仲間の技には「フラワーポイント（FP）」があり、基本的な技を除いて技を出す度にFPを消費する。つまり、マリオのFPが0になるとジャンプとハンマーの通常攻撃しかできなくなる。なお、仲間の攻撃も大半が使用時にマリオのFPを消費する。

状態異常 
敵の攻撃によってはマリオが何らかの状態異常を引き起こす場合がある。特定のアイテムなどで治せるほか、戦闘が終わると自動的に治る。マリオがバッジを利用した技を使用すると、逆に敵が状態異常を引き起こすこともある。
 毒
 マリオが緑色に変色し、数ターンの間、行動前に1ダメージを受ける。
 眠り
 マリオが眠ってしまい、数ターンの間何も行動できなくなる。防御のアクションコマンドもできなくなる。
 目回し
 マリオが目を回してしまい、数ターンの間何も行動できなくなる。防御のアクションコマンドもできなくなる。
 氷づけ
 マリオが氷づけになり、数ターンの間何も行動できなくなる。防御のアクションコマンドもできなくなる。
 ミニミニ
 マリオが小さくなり、数ターンの間攻撃力が半減する。

ほかに、一部の攻撃によってジャンプ・ハンマー・アイテムのいずれかが数ターンの間使えなくなることがある。

体力 
敵に与えるダメージは「（攻撃力） - （相手の防御力）」で計算され、あらかじめ設定されている「ハートポイント（HP） 」が0になったら敵が倒されるというものである。つまり、防御力2の敵の場合、攻撃力10の単独攻撃だと8のダメージを与えられるが、2×5回の連続攻撃だと1ダメージも与えられなくなる。ただし、防御力を無視して攻撃できる技もいくつか存在する。マリオの防御力は原則として0である。

仲間はHPが設定されておらず、受けたダメージと同じターン数だけ行動不能になる。そのため、仲間を攻撃する敵は少なく、受けたとしてもそのダメージは少ない。

戦闘中以外でも、フィールド上で溶岩やイバラに落ちることなどでマリオのHPが減る場合がある。マリオのHPが0になるとゲームオーバーになる。

バッジ 
冒険で手に入るバッジを装備すると、マリオに特別な能力が加わる。組み合わせは自由。ただし、マリオやバッジには「バッジポイント（BP） 」があり、バッジのBPの合計がマリオのそれを下回るように組み合わせなければならない。例えば、マリオのBPが「12」だと、合計が12以下のバッジしか装備できない。一般的に強力（有効）なバッジほどBPが高い。戦闘中はバッジの着脱が出来ないので、あらかじめ余裕のある時にバッジの調整をしておく必要がある。また、種類によっては、BPを使用せずとも装備できるものもある。レベルアップにより、より多くのバッジを装備できるようになっていく。

多くのバッジは名前がそのまま効果を表している。バッジによっては同一のものを複数入手できる。

レベル 
敵を倒すと、スターポイントが手に入る。手に入る数は敵の強さとマリオのレベルにより、同じ敵を倒してもマリオがレベルアップすると得られるスターポイントが少なくなる。また、原則的に手に入るのは戦闘終了後なので、途中で逃げると手に入らなくなる（ただし、特定のバッジを装備することで倒した分をもらうことができる）。

敵キャラの中には分裂や仲間の呼び出しなどをして無限に登場するものも存在し、マリオのレベルが低い状態でこれらの敵と戦うとスターポイントを稼ぐことが可能である（なお、一度の戦闘で手に入る最大のスターポイント数は100まで）。

スターポイントが100貯まるとレベルアップし、HP・FPが最大まで回復する。同時にこの3つのうちいずれかの最大値を5（BPは3）上げられる。

レベル27になるとどの敵からもスターポイントを得られなくなるので、レベル27が本ゲームの最高レベルとなる。HP・FPの限界値は50、BPは30（なお、HPとFPは特定のバッジでそれ以上上げられる）。

仲間にレベルはないが、各地にあるスーパーブロックにより「スーパーランク」にランクアップでき、攻撃力や技の種類が増える。はじめは1人につき1ランクしか上げられないが、「ウルトラストーン」というアイテムをビッグキューちゃんから入手することでもう1ランク上の「ウルトラランク」に上げられる。スーパーブロックは全部で16個（仲間8人×2ランク）あり、仲間全員をウルトラランクにできる。

星の精 
クッパとカメックババが宮殿に侵入した際、7人の星の精はカードの中に封印され、各ステージボスの手に渡っている。本作では彼らを助け出すことが目的となっており、1人助けるごとに話が先へと進んでゆく。

星の精を助けると、同時に特殊な技を教えられる。これを使うにはFPとはまた別にスターパワーと呼ばれるメーターが必要。スターパワーは戦闘中、1ターンが終わると自動的に少しずつ回復するほか、「ねがう」のコマンドを使用すると若干の回復が可能である。アイテムを使っての回復はできないがキノピオハウス（後述）に泊まれば全回復する。星の精1人に対して1スターパワーが与えられるため、スターパワーの最大値は7となる。

星の精の名前や技の効果は後述する。

その他 
セーブは各地にあるセーブブロックで行い（ステージクリア時でもセーブ可能）、ゲームを終了したときや途中で戦闘に負けてゲームオーバーになったときには前回セーブした状態から再開となる。

HP・FP・BPの振り分けが偏った場合、または偏らせたい場合はレベーラという人物に依頼することで、レベルアップと同じ要領で上記3つの何れかの最大値を任意で10（BPは6）上げられる。しかし、ほかの2つの能力が5（BPは3）下がる。BPが下がった場合、バッジが全て外れてしまう。

施設 
 キノピオハウス（宿屋）
 全てのパラメーターを最大まで回復してくれる。全国（クッパ城、ピーチ城はキノピオハウスではないが、効果は同じ）どこにでもあり、キノピオが経営している（星の国ではキノピオのかわりに星の子がやっている）からか、いつでも無料で使用できる。サムイサムイ村では、回復した後にテーブルの上に「さむイモ」というここだけでしか手に入らないアイテムが置かれている。キノピオは礼儀には厳しいようで、ノコノコ村でテーブルに乗って話しかけると注意されるが、心は広いようで、サムイサムイ村で村長殺害事件の容疑が掛かっていても利用できる。
 ショップ
 様々なアイテムを売買できるが、当然ショップがマリオにアイテムを売る値段（売値）のほうが、マリオがショップにアイテムを買い取ってもらう値段（買値）より高い。全国どこにでもあるが品数や価格設定は店ごとに異なり、寒冷地ではファイアフラワーが高値で売れるなど、上手く利用すれば金儲けもできる。また、アイテムを32個まで無料で預けられ、これはどこの店でも自由に取り出せる。基本的に同じアイテムでも、後から出てくるショップのほうが安い値段で買うことができることが多い。テレサショップはレサレサを仲間にする前は利用できない。また、キノキノざっか店はヘイホーに占拠された時（ハンマーで殴ると撤退する）、サムイサムイ雑貨店はサムイサムイ村でマリオに村長殺害事件の容疑が掛かっている時（「村長を殺した人にアイテムは売れません」と冷たく追い返される）は利用できない。クッパ城の店においては、クッパの手下が売っているだけあって全ショップ中一番値段が高い。
 道場
 シショーとその弟子がマリオに戦い方のコツを教えてくれる。また、彼らと闘って段位を得ることができる。ストーリーには無関係だが、一部の村の住民と段位の比較で楽しむことができる。
 郵便局
 仲間宛てに届けられた手紙を読むことができる。手紙の数はストーリーが進むごとに増える。
 キャシーの家
 キノコタウンにある。調理師キャシーがアイテムを料理し、別の物に作り変える。無料だが、その代わり料理が失敗しても責任は負ってくれない（失敗した料理は「しっぱいりょうり」となり、使うとHPとFPが1回復する）。最初は1つのアイテムを料理によって更に強化させることしかできないが、中盤でグルメヘイホーが持っていた「おりょうりのほん」を渡すと、2種類のアイテムを組み合わせて料理をしてもらえるようになり、新なアイテムに作り替えられる種類が増える（任意で1種類だけのアイテムでもできる）。ここでしかできないキャシー特製のアイテムも多い。
 バッジ屋
 キノコタウンにある、ロテンという人物とその息子が営む店。いつも3種類のバッジが置いてあり、訪れる度に種類が変わる。昔は別の所で珍しい食品売っていた。
 デアールの家
 キノコタウンにある、クルクルと回転する屋根が特徴の家。占い師デアールが行くべき場所を占ってくれる。一回5コイン。
 ミステールの家
 星の降る丘にある。一階のミステール（姉）はアイテムが隠されている場所を占ってくれ、二階のアツメール（弟）は星のかけらとバッジを交換してくれる。占いは対象によって料金が異なり、星のかけらが5コイン/回、バッジが20コイン/回、スーパーブロックが30コイン/回となっている。
 占った対象が、手の届かないような状態になっている場合（スーパーブロックを占ったが、既に全て取った後や現在の進行可能範囲にない場合など）は、料金を全額返してくれる。
 また、ここにある「不思議な宝箱」という名前の宝箱はキノコ城にある同じ宝箱と繋がっており、ピーチが見つけたアイテムをマリオに送ることができる（逆にピーチ姫に送ることはできない）。
 サンデールの家
 カラカラタウンの奥にひっそりと建っている。自称「さばくのキュートなまじないし」・サンデール（ミステールの妹）が戦闘時にステータスを高めたり、スターポイントやコインを増やしたりするまじないをしてくれる。ただし、どのタイミングで何が起こるかは全くのランダム。なお、払ったコインが多いほど、効果の期間や確率が高まる。ミステールとサンデールは双子である。
 遊技場
 キノコタウンに隠されていて、ミニゲームが遊べる。2種類あるが、それぞれ遊ぶのにメンバーズ・カードが必要。メンバーズ・カードは両方ともノコジロウからもらえる。
 牧場
 ゲームの進行には全く関係ない施設。キノコタウンにある。巨大なガチャポンの機械が置いてあり、1回10コインでブーブーさんというブタを出せる。ブーブーさんは11匹になると1匹がアイテムを残して逃げるが、このアイテムを取りに行くと全て逃げてしまう。ブーブーさんにはさまざまな種類がおり、近くにいるキノピオに聞くと、出てくるブーブーさんについて色々と教えてもらえる。
 列車
 キノコタウンとゴツゴツ山を結ぶ路線。駅は両端の2駅しかない（物語の最後にはカラカラタウンまで開通している）。特にダイヤが設定されていないようで、駅員に話しかけると好きな時に汽車を出してもらえる。ただし、方向転換の関係で、一旦利用すると画面を切り替えてからでないと再度利用できない。使われているのは『マリオカート64』にも登場したK64という蒸気機関車。単行のため、マリオ達は機関室に乗る。
 電車
 おもちゃ箱の中を環状運転している。利用の仕方は列車とほぼ同じだが、乗る前にあらかじめ進行方向（右回り又は左回り）を決める必要がある。車両が無いのでどこかから調達してくる必要があったり、線路がヘイホー達に壊されているので修復しながら走らなければならなかったりと、運行に障害が多い。
 星の渡し舟
 星の国とクッパ城間を結ぶ小型の飛行艇。外観はバスタブに似ている。翼はおろか動力すら見当たらず、どのようにして飛んでいるのかは不明。地上にいる人からには流れ星に見える模様。

登場キャラクター 
 
（）と書かれている名前は北米版での表記。

仲間 

マリオ（Mario）
 このゲームの主人公。捕まった星の精達を救出すべく、キノコ王国の各地を飛び回る。基本となるジャンプ（踏みつけ）とハンマーに多くのバッジを組み合わせることにより、多彩な攻撃をすることができる。
クリオ（）（プロローグ・マリオの目が覚めてクリオに話し掛けたあと）
 クリボーの少年でマリオのファン。青い帽子をかぶっており、まだ少年なのか、牙の代わりに普通の歯が生えている。一人称は「オイラ」。クリオという名はマリオにあやかってつけられたという。頭が良く、ステージや敵の情報を教えてくれる（しかし、なぜクッパの最終形態の特徴まで詳しく把握しているのかは不明）。「ものしり」を使うと敵のステータスを知ることができ、一度調べた敵に対しては残りHPが常に表示されるようになる。攻撃は頭突きしかできない（逆に言えば、仲間の中で唯一甲羅のある敵（ノコノコ、メットなど）をひっくり返す事ができる）ので、トゲを持った敵や炎を纏った敵には攻撃することができない。レベルアップをすると、チャージや連続攻撃ができるようになる。ものしりは通常でも使うことができ、いろいろな土地や人物の情報を毒舌や皮肉をまじえて詳しく教えてくれる。
 本人は、ミステールのような年上のお姉さんには弱いと言っている。
カメキ（）（ステージ1前半・｢カメキのこうら｣を返したあと）
 考古学者チャールズに憧れるノコノコ。青くて硬い甲羅を持ち、赤いリストバンドとスカーフを愛用している。一人称は「オレッチ」。弟分気質で語尾に「〜ッス」を付ける。初期の段階で全体攻撃技を使えるという利点があり、甲羅に身を潜めて攻撃するため、FPを使わない攻撃でもトゲや炎に覆われている敵の反撃を受けない。また、炎属性の技が覚えられるため、氷属性の相手に大きなダメージを与えることができる。ただし、全て体当たり攻撃なので空中の敵には攻撃できない。レベルが上がれば目回しなどの状態変化を与える攻撃も覚えられるようになるが、最後まで空中への攻撃手段は覚えない。フィールド上では、離れたスイッチを押したり、遠くのアイテムを取ってきたりすることができるほか、敵に対して先制攻撃をすることもできる。クリオの話ではキューちゃんのことをかわいいと思っていないらしい。仲間にしてほしいという頼みを断ると、｢そりゃあないっすよマリオさん｣と言いなおも断り続けても同じセリフの繰り返しである。また、クリスター神殿のにてカメキの偽物（と言ってもカメキそっくりでなく全く別のキャラになっているため偽物ははっきりしている）を叩いていくシーンで、わざとカメキを叩くとカメキがマリオに初めて怒るところが見られる。
ピンキー（）（ステージ1後半・ノコブロスの罠で牢屋に閉じ込められたとき）
 ノコブロスの砦に捕らわれていた、チャキチャキしたピンクボムへいの女の子。一人称は「あたい」。4つの技のうち、全てが攻撃技。爆発を使った攻撃を得意とし、特定の敵には絶大なダメージを与えられる。FPが高い代わりに威力があり全体攻撃も可能。ただし、体全体が甲羅に覆われているメットなど、爆発が効かない敵も存在する。かつては砦で働いていたが、ノコブロスの人使いの荒さに耐えられず、反抗したことにより閉じ込められた。フィールド上でも爆発が可能で、この爆発は最強の先制攻撃であるが、ほかより仕掛けるのが難しくシビアである。また、爆発時のエフェクトはレベルが上がるたびに豪華になる。敵のボムへいは爆発すると消え去ってしまうが、彼女や敵でないボムへいは何度爆発してもすぐに復活する。
パレッタ（）（ステージ2、3通の手紙をパレッタに返したとき）
 キノコタウンにある郵便局の配達員をしているパタパタ。一人称は「わたし」で、丁寧な口調である。手紙をキノコワールド中にばらまいてしまい、３通の手紙を探し集めている途中でマリオと行動を共にして仲間になる。彼の父親曰く「のんびり」とのことだが、クリオによれば、その性格が人気をよんでいるらしい。マリオや敵を持ち上げて運ぶことができる。戦闘時は対応が辛い空中や天井の敵に強く、「パレッタシュート」と「みだれとび」は甲羅に身を潜めて攻撃するためトゲや炎の敵の反撃も受けないので、使い勝手が良い。登場自体は全キャラにおいてもかなり早く、オープニングでマリオにパーティの招待状を届けにきていた。『ペーパーマリオRPG』にもオープニングで登場した。仲間にしてほしいという頼みを断ると、カメキとは違って諦めが早くしょんぼりする姿が見られる。また拾った手紙は、仲間になった後で宛名の人に渡すことができるが、パレッタの状態にしなければ渡すことはできない。
レサレサ（）（ステージ3、迷い森の奥にある「テレサの屋敷」の3階にマリオが辿り着いたとき）
 テレサのおやしきのお嬢様で、一人称は「あたくし」。薄緑色の体で、頭に赤と黄色のリボンを付けている。性格は極めて高飛車で、気に入らない相手に対しては容赦なくビンタを仕掛ける。常に手にしている扇子もハリセンとして武器になる。しかしただ高飛車で高圧的なだけではなく、ドガボンにも物怖じしない気丈さを持ち、マリオと共に自ら成敗へ赴くなどの行動力の強さから、テレサたちの信頼も厚く、テレサ曰くみんなのアイドルらしい。ドガボンを倒すことを条件に強引に仲間になる。連続で小ダメージを与えるビンタ攻撃は、防御力が0の敵に対しては合計ダメージが他の仲間より多くなり、特にハリセンビンタは強烈。ただし、一撃の攻撃力が低いため高い防御力を持つ敵とは相性が悪い。なお、バトル中でもマリオの姿を消す事ができる透き通り技を使えるが、この技を使った直後のターンは行動不能となる。この作品で登場するテレサは全てマリオの味方や協力者であり、対人恐怖症の者はいない（お化けらしく、驚かす者もいる）。『ペーパーマリオRPG』でも登場。
アカリン（）（ステージ4、「ビッグカンテラくん」を倒したあと）
 ケセランの赤ちゃん。一人称は「あたち」(ただし、アカリンの場合が多い)。性格は幼いが、ビッグマウスな一面をもつ。ビッグカンテラくん（彼女曰く「ウヒヒヒィのイヤなヤツ」）に誘拐され、カンテラの光に利用されていたが、そこをマリオに助けられたのを機に仲間になる。カンテラをハンマーでなくピンキーの爆発で壊した場合、「そんな乱暴な事、よく思いつきまちたねー」と怒られる。通常攻撃は相手の防御力を無視できる。暗い部屋を明るくしたり隠しブロックを見つけたりでき、アカリンを持ちながら歩くことも可能。自分自身が電気を出していることもあり、電気攻撃は無効。ただし、攻撃技の4つの中でダメージを与えられる技は1つしかないことが弱点となるが、全て援護系の技なので使い勝手は良い。
おプク（）（ステージ5、子供の罠にハマった彼女を助け出したとき）
 お節介なプクプクのおばさん。口調からして他のキャラクターに比べかなり高齢であり、娘もいる（存在自体は郵便局への手紙で確認可能。夫が健在かは不明）。一人称は「あたしゃ」で、面倒見はかなり良いようである。ただ、子供の罠に引っ掛かるなど、多少ドジであることもうかがえる。ロマンスや感動を誘う物事には非常に弱く、マリオの仲間になった理由も彼の本意に触れて感動したからである。本人も公式サイトのキャラ紹介で「水の事に関してはエキスパートだからね」と語っており、水中ではマリオを乗せて移動することができ、戦闘時は水を使ってマリオの攻守をサポートする。攻撃力は仲間の中でも高く、様々な形で攻撃が行えるが、アクションコマンドが仲間の中でも難しく、特に「ジェットふんしゃ」はプレイヤーの冷静さと正確さを必要とする。仲間キャラの中では唯一、特殊能力を発動できる場所が限定されている（目印として、水辺に木の板が敷かれている）。
ポコピー（）（ステージ6、「ジョナサン?」とのバトルに勝利したあと）
 ビッグな男を目指すツッパリジュゲム。一人称は「オレ」。初登場時は「ジョナサン」と名乗っていた（理由は本人曰く「ポコピーはポコっとしたピーってイメージがあるから」らしい）。見た目によらずロマンチストな面もあり、マリオとの勝負を「男同士の戦い」として楽しむ。ポコナ（Lakilulu）という彼女がおり、フライトという友達もいる。ほかのジュゲム（オズモーンの手下）を裏切ったことになるが、本人はさほど気にしていない。パイポを投げて戦うが、トゲゾーを作り出す事は出来ない。少ないFPで全体攻撃を可能とする。仲間キャラの中で唯一、敵に触れないで相手に攻撃するので相手を選ばないが、突出して強力な攻撃技は使えず、「みだれなげ」はコマンドが失敗するとダメージが0になる。名前の由来は種族名のジュゲムと同じく落語の寿限無の一部からであり、ポコナも同様である。

また、これらの8体の仲間は『スーパーペーパーマリオ』のカードとして登場している。

星のせい 
チョール（Eldstar）
 髭を生やした黄色の星。7人の中で最も偉い。
 一人称は「わし」。砦でノコブロスに捕まっている。助けるとHP・FPを5ずつと状態異常を回復させる「すっきりそうかい」という技と、星の精を使ったアクションの方法を教えてくれる。
 スターパワーの色は黄色。必要スターパワーは1。マリオのことは呼び捨てで呼んでいる。漫画版では強引で自己主張の強い面が出ており、やたらとボケをかます。
マール（Mamar）
 リボンを付けた黄色の星。
 一人称は「あたし」。遺跡でカーメンに捕まっている。助けると敵全体を眠らす「ママのこもりうた」という技を教えてくれる。
 スターパワーの色は黄緑色。必要スターパワーは1。マリオのことは「マリオちゃん」と呼んでいるが、漫画版では呼び捨てになっている。
ハール（Skolar）
 眼鏡をかけた紫色の星。
 一人称は「わがはい」だが、漫画版では「わたし」。元々はピューピューヒルでドガボンに捕まっていたが、隙をうかがい脱出していた。しかし、星の降る丘に向かう途中、迷いの森で迷っていたところをテレサ達に捕まえられた。そのため、マリオがボスのドガボンを倒さない限り解放してもらえないと、レサレサから威嚇を受ける。助けると敵全体に7ダメージを与える「ほしのふるよる」という技を教えてくれる。
 漫画版ではまよいの森で倒れているところをテレサ達に助けられ、マリオ達にその恩をかえしてほしいと頼む。後にマリオ達がやられている時にマリオ達の前に現れ、ハール自身の技「ほしのふるよる」をドガボンに発動した。
 スターパワーの色は水色。必要スターパワーは2。また、口はあるが、漫画版では無い。マリオのことは「マリオくん」と呼んでいるが、漫画版では呼び捨てになっている。
ニール （Muskular）
 帽子を被った水色の星。一人称は「ぼく」。
 おもちゃ箱でしょうぐんヘイホーに捕まっている。助けると敵全体の攻撃力を落とす「ちからをぬいて」という技を教えてくれる。
 漫画版ではゲームとの性格が逆になり、ボケキャラである。また、しょうぐんヘイホーを倒したときに、救出された時にはしょうぐんヘイホーの戦車の中にいたため、ボロボロの状態で救出された。
 スターパワーの色は青色。必要スターパワーは2。マリオのことは「マリオくん」と呼んでいるが、漫画版では呼んでない。またひどいボケキャラになっている。
ネール （Misstar）
 羽衣をはおったピンク色の星。一人称は「わたし」。
 火山でファイアパックンに捕まっている。助けるとHPを20回復する「おねえさんのキス」という技を教えてくれる。
 スターパワーの色は紫色。必要スターパワーは3。マリオのことは呼び捨てで呼んでいる。漫画版では表情が笑顔になっている。
テール（Klevar）
 蝶ネクタイを付けた黄色の星。一人称は「ボク」。
 雲の上でオズモーンに捕まっている。助けると敵全体の動きを止める「じかんよとまれ」という技を教えてくれる。
 スターパワーの色は赤紫色。必要スターパワーは2。マリオのことは呼び捨てでと呼んでいるが、漫画版では「マリオくん」になっている。
ダール（Kalmar）
 髭を生やした黄色の星。
 神殿でパラレラーに捕まっている。助けると敵全体を星に変えて打ち上げる「そしておほしさまに」という技を教えてくれる（ただしこの方法で敵を倒してもスターポイントは貰ず、ボス戦で使用しても当然倒すことは出来ない）。
 スターパワーの色は赤色。必要スターパワーは2。マリオのことは「マリオくん」と呼んでいるが、漫画版では不明。

全員揃うと、スターの杖の力を無効化する「スターフラッシュ」という技が追加される。この技は最後のクッパ戦においてスターの杖の効果を打ち消すためのものだが、通常の敵にも使え、その際にはパワーアップやチャージを打ち消す。クッパ戦の途中でスターの杖がパワーアップして効果を打ち消せなくなるが、その時は星の子のティンクが加わってスターフラッシュが「ピーチフラッシュ」にパワーアップし、スターの杖の効果を完全に打ち消せるようになる。必要スターパワーはなし。

なお、この星のせい達は『マリオパーティ5』にも登場した。

主なサブキャラ 
ピーチ姫（Princess Peach）
 キノコ王国を治める姫。今回は城ごとさらわれてしまうものの、自分の部屋に仕掛けられていた隠し通路を発見したことから、何度もこっそり部屋を抜け出し、ティンクと共にマリオのために情報やアイテムを集めている。
ティンク（Twink）
 最近になり星の国に来た星の子。ピーチ姫の部屋に願い事を聞きにやって来たのをきっかけにピーチとマリオの架け橋となる。
キノピオ（Toad）
 多くがピーチ姫の家臣となっている。それ以外の者もショップの店員や宿屋の管理人など人助けをする職業に就いている人が多い。
キャシー（Tayce T.）
 キノコ城の調理師をしている女性キノピオ。クッパがキノコ城を持ち上げる前に逃げ出した。アイテムを持っていくと、様々な料理に作り変えてくれる。ヘイホーにフライパンを盗まれてしまう。また、グルメヘイホーが落とす「お料理の本」を渡すと、レパートリーが増える。ダンナとは死別したとのこと。
 『スーパーマリオUSA』などに登場するキャサリンのあだ名もキャシーだが関係は無い。
ロテン（Rowf）
 露天商。息子（名前はコロテン（Rhuff））と一緒に色々な土地で色々な物を売り、キノコタウンでマリオにバッジを売ってくれる。ただし、どのバッジもかなりの高額。クリア後のエンディングでは店じまいして他の場所に店を出すと言っているが、息子の頼みを聞いて一日だけパーティのためにキノコタウンに滞在する。その後のエンディングパレードの様子から察するに、ロレンチュと交渉してカラカラタウンに店を出すようである（どんな物を売るかは不明）。『ペーパーマリオRPG』でも似たようなキャラクターが登場する。
デアール（Merlon）
 キノコタウンの占い師。マリオたちの行く先を5コインで占ってくれる。相当な変わり者で、最初は家を訪ねても「デアールはるすであーる!」と居留守を言ってなかなか家に入れてくれない。語尾に「であーる」を付けて話し、大変な長話をする癖がある。後述するデアールの先祖からして、長話は一族の伝統らしい。
 なお、デアールの一族は『スーパーマリオRPG』に登場した魔法使いのキャラクター「スペール」がモデルとなっている。
シショー（The Master）
 キノコタウンにある道場の師匠。ゲーム本編とは関係なく、腕試しとして最大3回戦うことができる。負けてもゲームオーバーにはならない。勝利する度に段位がもらえる。チェン（Chan）、リー（Lee）という2人の弟子がおり、最初は彼らと戦うことになる。なお、先述のキャシーとはきょうだいの関係にある。
キノポン（Russ T.）
 キノコタウンに住む物知りで情報を提供してくれるキノピオ。攻略情報やちょっとした裏話などを教えてくれる。ただし、ヘイホーに辞書を盗まれた時は辞書が戻るまで情報を聞くことができない。
ミステール（Merluvlee）
 デアールの孫娘。星のふるおかで占い屋をしている。バッジや星のかけら、スーパーブロックのありかを教えてくれる（料金は内容によって異なる）。
アツメール（Merlow）
 デアールの孫でミステールの弟。集めた星のかけらとバッジとを交換してくれる。
ハテナ虫（Chuck Quizmo）
 謎のイモ虫。ステージのどこかに現れ、マリオに合計64問のクイズを出す。正解すると「ほしのかけら」をもらえる。間違えてもペナルティはなく、同じ問題に再挑戦出来る。正解・不正解にかかわらず、1問答えるごとにハテナ虫は場所を移動するが、ある程度は登場する場所は決まっている。なぜか星の国にも出現する。
キノピコ（Vanna T.）
 ハテナ虫のアシスタントである女性のキノピオ。本編では一言も喋らない。次作『ペーパーマリオRPG』のほか、『マリオカート ダブルダッシュ!!』『マリオテニスGC』『マリオパーティ8』などに同名のキャラクターが登場しているが、別人である。
グルメヘイホー（Gourmet Guy）
 美食家。「グルメヘイホー」の名は周りからの呼び名であり、本人は普通のヘイホーのつもりでいる。常に左手にナイフ、右手にフォークを持っており。洋食好きで、特にケーキがお気に入り。おいしいケーキを食べると、大声で叫びながら飛び回る癖がある。ヘイホーのおもちゃ箱の中に登場するが、飛び回った弾みではるか上空にあるキノコ城にまでたどり着き、そこで出会ったピーチにもケーキ作りをさせる。クッパ軍団の一員だが、のんびり屋かつ恩を忘れない性格。ケーキを作ればピーチを見逃してくれるうえ、星の精に関する情報をピーチとティンクに提供する。
クリオの家族
 クリ村で生活しているクリオの家族たち。妹のクリコ（Goombaria）に、両親のクリパパ（Goompapa）とクリママ（Goomama）、祖父母のクリじい（Goompa）とクリばあ（Gooma）という家族構成。
 祖父のクリじいは、かつてノコジロウとセバスチャンと共に旅をした冒険家で、現在も高齢ながら元気。かつては有名な格闘家であり、クリオがウルトラランクで覚える「れんぞくずつき」も昔のクリじいの技であったという。また、道場にいるシショーの先生をしていた。プロローグの一定期間の間マリオと行動しレクチャーをしてくれる。
 父のクリパパは釣りが趣味。ある場所に落ちている彼宛の手紙を届けると、彼の釣り仲間を初めとするいろいろな人物に手紙を渡すリレーイベントが始まる（ゲームクリアに必須ではない）。
ノコジロウ（Koopa Koot）
 ノコノコ村の長老にして村一番の長生きカメ。高齢で喋り方がぶれるためか、彼の台詞の字幕表示は常に揺れている。わがままで、マリオに計20回もの頼みごとをする。マリオが頼みごとを聞いても基本的にコイン1枚しかくれないが、ときどき遊技場のカードや星のかけらなどの貴重なものをくれる。実はルイージのファン。冒険家の中では唯一、家族や仲間（現在）がいない。
ボムへいたち（Bob-omb）
 ピンキーと共にノコブロスの砦に捕まっていたボムへいたち。大抵の人物の口癖は「〜ボム」。クッパ軍団入りしたことで高圧的で人使いが荒くなったノコブロスに自爆攻撃をしたため投獄されたらしい。ノコブロスが倒された後は行くあてもないらしく、カメキの家に勝手に住み着いているが、カメキ（家主）が帰ると家を追いだされるのではないかと心配している（ただし、家主がカメキとは知らない様である）。このうち、「ブルース（Bruce）」という青ボムへいはピンキーに熱烈なラブコールを送り続けているが、ピンキーからは非常に嫌がられている。
コブロン（Whacka）
 ゴツゴツ山にいる、水色のモグラのような生物。口癖は「フニャ～」。ハンマーで殴ると「タンコブ」というHP・FPを25ずつ回復するアイテムが手に入る。殴るごとに少しずつ怒り、8回(ストーンハンマーの場合6回、メタルハンマーの場合は4回)殴るとそれ以降は現れなくなる。後に毎シリーズに登場するキャラとなる。過去にはもっと仲間がいたと本人は語っているが、人々が美味しいタンコブを求めて叩き続けたため、数が減っていったという。これが最後の1体だと思われていたが、後に『ペーパーマリオRPG』のトロピコアイランドに、『スーパーペーパーマリオ』のストンストンランド（ただし、こちらは異次元の世界である。それどころかタンコブを無限に手に入れられるところすらある）にもいることが確認された。
 『MOTHER』好きな開発者がフライングマンへのオマージュとして考案した。
チャールズ（Kolorado）
 カメキが尊敬する考古学者。行く先々でマリオ一行と遭遇する。探検家だが気が早く、ステージ5ではマリオ一行に迷惑を掛け続けた。宝物に関しては目がなく、マグマが迫っている時でも宝物を探し出そうとするほどである。また、恐妻家のため、妻には頭が上がらない。かなり悪運が強いのか、溶岩に落ちようが崖から落ちようが、巨大な岩に押し潰されようが、直後には元気になっている。ステージ5の終わりでは星の精（ネール）を「ヒトデ」とよんでいた。なお、続編の『ペーパーマリオRPG』ではゴンババ城のカメの亡骸を調べると手紙の相手に我が息子チャールズへと書いてある。
 これまで探検したのはアラビン遺跡（最初は遺跡近くの砂漠にキャンプを張っているが、マリオの家に手紙（既にマリオが攻略した事は知らない）が届いた後には引き払っている）、ジャンボル島（単独でマリオたちと同行）。エンディング後は妻に内緒でカメキを案内人としてクリスター神殿に行こうとするが、パレッタから妻が怒っていることを聞き、諦めている。
ロレンチュ（Moustafa）
 カラカラタウンの首領。用心深く人を見る目もあるが、結構なワガママ。古代アラビン王国の子孫らしい。チューの中で体が緑色なのはロレンチュだけである。不用意にアラビン遺跡の秘密を与えないため、普段は「モノクレー」と名乗り、情報屋として活動し、来た者の様子を探っている。レモンが好きで、モノクレーとしての彼にレモンを渡すとロレンチュに会う方法を教えてくれ、その方法に従うと正体を明かし、アラビン遺跡を探す為のピカピカストーンをマリオに渡してくれる。名前は『アラビアのロレンス』が元ネタ。
サンデール（Merlee）
 デアールの孫娘。ミステールの双子の妹で、アツメールの姉。
 カラカラタウンで「おまじない屋」を営んでいる。プレイヤーでも気づきにくいほどの、ひっそりとした場所に店を構えている。
 モーリー（Oaklie）
 迷いの森を守っている人物。最初はマリオを迷いの森へ行かせてくれないが、テレサのお屋敷に行くときになると通してくれるようになり、迷いの森の抜け方を教えてくれる。その後は、迷いの森の中にいる。
セバスチャン（Bootler）
 レサレサの執事。常にレサレサの身を案じているが、本人からは煙たがられている。マリオをテレサの屋敷に招待する。過去にノコジロウ・クリじいと共に旅をしたことがある。
クジラ（Whale）
 体内でケムシが暴れて困っている。助けると、キノコタウンからジャンボル島間の船代わりになってくれる。チャールズがマグロと誤解して人々に話をしたため、一般的にはこちらの方が広く伝わっている。
ヨッシー（Yoshi）
 ジャンボル島のヨッシー村に住む種族。子供達（チビヨッシー（Fearsome 5））がいなくなり、心配している。色は赤・青・緑・黄・紫・茶の6色。黄色のヨッシーは美味しい料理には目が無い。
 なお太った緑色のヨッシーは村長。
ビッグキューちゃん（Raphael the Raven）
 ジャンボル島の主である巨大キューちゃん。『スーパーマリオ ヨッシーアイランド』でボスキャラクターとして登場したことがあるが、別人のようである。
 フラワーさん（Bub-ulb）
 頭に花を咲かせており、話しかけると花の種をくれる（ただし最後の１つはチャールズからもらう）。4つ全て集めないとゲームクリアは不可能。
リップ（Minh T.）
 キノコタウンでガーデニングをしているキノピオの女性。フラワーさんと仲が良く、フラワーランドの危機を伝えられた。名前は本作と同じくインテリジェントシステムズが開発しているゲーム『パネルでポン』の初代主人公、花の妖精リップから。
コボック（Wise Wisterwood）
 フラワーランドに生えている古木。動けないが、会話は可能（以下の花も同様）。理由は不明だが、キノコタウンへの扉と同化している。
 ハナコ（Petunia）
 フラワーランドに咲くパンジー。タネマニアのハナコと呼ばれ、「種のままの方が自由だから」という理由で植物を種のまま育てずに集めている。自分の周りを荒らすフラワーチョロプーに困っており、悩みを解決するとマメの種をくれる。
ユーリー（Posie）
 フラワーランドに咲くユリ。たずねると「ゆたかなつち」をくれる。平時はやさしそうな口調だが、怒るとドスの効いた口調になる。横に生えているクリスタルの木とは根が絡まっており、叩くと痛みが伝わる。警告を無視して叩き続けると怒り始め、それでも止めないと出入禁止にされる（なおその後何回かユーリーに会ったら許してくれる）。
スイレーン（Lily）
 フラワーランドに浮いているスイレン。池の水が抜けて困っている。解決すると、水を分けてくれる。結構メルヘンチックな性格。
バーバラ（Rosie）出入禁止
 フラワーランドに咲くバラ。スイレーンの池を元通りにすることができる水の石を持つが、性格が悪く素直に渡してくれない。フラワーランドで一番美しいのは自分と主張しており、それが理由でスイレーンと張り合っているとのこと。フラワーランドの危機に関してはあまり気に留めていなかった。
ウソツキ草（Tolielip）
 フラワーランドに咲くキンモクセイ。目が細く出っ歯。彼の言っていることの大半はデマだが、その反対のことを行うと良いことがあることが多い。
太陽（Sun）
 フラワーランドの「太陽の塔」にいる太陽。オズモーンが晴れることのない曇り空を作ってしまったため、やる気をすっかり失っている。クモクモマシーン破壊後はやる気を取り戻した。
???
 フラワーランドにある井戸に住んでいる謎の人物。井戸に「あおいみ」を投げ入れると、喜んでバッジ「フラワーセツヤク」をくれるが、それ以外の色の実を投げ入れるとハッチーやパンジーさんなど敵キャラが井戸から出てくる。
サムイサムイ村の村長（Mayor Penguin）
 マリオが村を訪れた際、自宅で倒れていた。周囲からは死亡したと勘違いされ、第一発見者となったマリオが「殺人」ならぬ「殺ペンギン」犯として疑われることとなる。実際には気絶しただけで、周囲の勘違いが解けた後は「すばらしいバケツ」をくれる。オープニングのパーティでも登場している。
ゴンベエ（Herringway）
 サムイサムイ村の作家。倒れていた村長が持っていた紙に彼の名前が書かれていた。　
 エンディング中キノコタウンにいるペンギンの発言からして、本作『マリオストーリー』は、本作中のマリオの冒険を彼が書籍化（及び誰かがそれを絵本にした）したものと設定されている。
 続編の『ペーパーマリオRPG』にて、推理小説がベストセラーになり、ピカリーヒルズに別荘を買ったことが判明する。
スタール（Merle）
 星の生まれる谷の責任者。デアールの息子で、ミステール・サンデール・アツメールの父。一族には珍しく長話を好まない。訪れると雪だるまの謎を解く伝説のマフラーをくれる。
ハックン（Ninji）
 星の生まれる谷で星の子の面倒を見ている。ステージ6終了後、デアールの家に訪れる。
キタピオ（Frost T.）
 星の生まれる谷で星の子の面倒を見ているキノピオ。オープニングのパーティでも登場している。
クリスタール（Madam Merlar）
 デアール達の先祖で、クリスター神殿への道を守っている。デアールと同様に非常に長話。神殿を荒らすクッパの手下達を倒し、ダールを助け出してもらうべく、代々守られていたスターストーンをマリオ達に渡す。
 後に『スーパーペーパーマリオ』でも登場している。
ルイージ（Luigi）
 前作の例に漏れず、家で留守番をし続けている。今回は傍らで密かに家を増築し、その中で秘密の日記を書いているほか、エンディングのパレードではさりげなく先頭で先導しているなど、ちゃっかりした一面も見せている（パレードの先頭にいるのは前作の『スーパーマリオRPG』と同じ）。日記には、「兄さんだけズルイ」や「前のゴルフやパーティやテニスは楽しかった」（それぞれ『マリオゴルフ』『マリオパーティ』『マリオテニス』のこと）などとグチをこぼしている。チャールズの件で例に漏れず、クジラをマグロと間違えている。また、この日記の中で「実はボクはオバケの類が大の苦手なんだ」と告白しており、この設定は事実上、後に発売される『ルイージマンション』への伏線になっている。夢は日記によると2段ベッドの上段に寝る事（実際はマリオが2段ベッドの上段で、ルイージが2段ベッドの下段。なお、このベッドでもキノピオハウス同様の効果で休む事ができる）。
 本作のテレビCMでもマリオが「毎日ゴルフにパーティに、近頃はテニスも始めて、何か忘れているような…そうだ！冒険だ！」と言うネタがあった。

敵キャラクター 
クッパ（Bowser）
 本作のラスボス。クッパ軍を指揮し、スターの杖を悪用してピーチ姫を自分のものにしようと企んでいる。
 様々な過去作品でマリオに邪魔をされてきた経験からか、本作ではストーリーの序章にて星の国を襲撃し「スターのつえ」を手に入れてパワーアップしている。また、その際スターのつえを守る星の精達をカードに封印し、キノコワールド各地のボスに守らせている。スターのつえを手に入れたため、かなり慢心している様子が見られる。
 プロローグにてキノコ城の地下に潜ませていたクッパ城を遙か天空に浮上させ、ピーチ姫をキノコ城ごとさらう。その日、行われていたパーティに出席していたマリオに妨害をうけるも、前述のスターの杖でパワーアップしたことでマリオを圧倒し、地上に落とす。その後、ピーチ姫と何度も仲良くなろうとするが、毎回断られる。また、カメックババと共に何度もマリオの冒険の邪魔をするが、マリオが各地のボスを撃破したことで、星の精を解放させてしまう。決戦では、星の精の力でクッパ城、キノコ城に再びやってきたマリオと再戦する。スターの杖で無敵になるも、スターの杖の力を星の精に破られ1度は倒される。だが、カメックババに作らせた装置の力でスターの杖の力をさらに増幅させて再戦する。最終決戦では、パワーアップを果たして星の精の力をも跳ね返すなど再度優位に立つ。その際「キサマではワガハイにはかてぬのだ！」と豪語するも、星の精の力に加えて、ピーチとティンクの願いが込められた「ピーチフラッシュ」により破られマリオに再び倒された。「むてきになったのになぜかてないのだ」と悔しがり、最後まで敗因に気づけなかった。
 戦闘中に二度体力を大回復させるため長期戦になりやすい。漫画版ではこの演出は「マリオがクッパの足のツボを刺激したことで元気にさせてしまった」というものになっている。
カメックババ（Kammy Koopa）
 クッパの腹心。箒で空を飛び、マリオの行く先々で様々な罠をしかけ、冒険を妨害をする。主にブロックや敵キャラをステージに設置するが、プレイヤーの選択によってはピーチに騙されお助けアイテムを設置することもある。この他にも、星の精に関する知識を持っていたり、ピーチ姫の変装を見破るなど油断できないキャラでもある。
 マリオとは戦闘を行わないが、ステージ８のクッパ戦中にピーチとティンクを操作して戦うこととなる。その際は魔法でブロックを生成して攻撃してくる。
コワッパ（Jr. Troopa）
 クリオの故郷であるクリ村周辺のガキ大将。通信販売とトレーニングが趣味で、自分よりも強い者に勝つことに執念を燃やす。彼については、クリオ一家しか知らない様である。プロローグでマリオに負けたため、打倒マリオを目標にストーリー中何度となく登場することとなる（クッパ城にも登場するが、クリオの言う通り、どうやって来たのかは不明）。気合と根性は凄まじいが、どこか空回りしていることが多い。#キャラクターの項も参照。
 戦うたびにパワーアップしており、攻撃力と防御力のアップ、飛行状態やトゲ付き、最終的には通信教育で覚えた強力な魔法攻撃を仕掛けるなどかなり手強い敵となる。
クリキング
 プロローグのボス。王冠やマントを身につけた巨大なクリボー。クリ村とキノコタウンの間に砦を築いて封鎖している。クリレッド・クリブルーが配下におり、共にマリオと戦うが、倒される。その後は、マリオがキノコタウンに繋がる道のスイッチを押したことで砦が崩壊し、その反動で遠くに飛ばされた。
 クッパに「王様になりたい」という願いをスターのつえで叶えてもらった。
ノコブロス
 ステージ１のボス。4人組のノコノコで、それぞれレッド、イエロー、グリーン、ブラックのカラーがついている。ぽかぽかロードの先にあったボム兵の砦を乗っ取り「ノコブロスのとりで」として根城にしている。変装や落とし穴、クッパに似せた戦闘マシーンを用いてマリオを妨害する。
 戦闘時は4人が積み重なった状態で戦う。必殺技は4人一組で繰り出される「ノコブロス・スクリューアタック」。POWブロック等を使うと崩れてしまい、通常のノコノコと同じようにひっくり返ってしまう。ピンキーの爆発攻撃を使うと1発でひっくり返せる。
 ボム兵をかなりこき使っていた様子で、反抗したボム兵を牢屋に閉じ込めていた。ボム兵曰く「1日25時間働かせられる」とのこと。その反動か、自分達が負けて牢屋に閉じ込められた際は誰も助けてもらえなかった。撃破後、しばらく牢屋に閉じ込められている様子を見られるが、途中でいなくなり、ステージ８のクッパ城で再登場を果たす。しかし再戦は叶わず、代わりに乱入してきたコワッパとの戦闘となる。
 漫画版では1巻に彼らとよく似たコンセプトの敵が登場している。
カーメン
 ステージ２のボス。古代エジプト風の衣装に身を包んだカメ。カラカラ砂漠の地中に埋もれていたアラビン遺跡に潜り込んでいた。
 戦闘では甲羅投げや魔術を使うほか、ワンワンを使役する。しかし、2回目の魔法攻撃は自分に降りかかり、しばらく行動不能となる。そのため、倒すには絶好のチャンスとなる。
 漫画版ではマリオたちを追い詰めるも、カメキに恩のあったストーンワンワンに反旗を翻され敗北する。
ドガボン
 ステージ３のボス。一回り以上大きなガボンへい。ピューピューヒルの頂上にある城にいる。どんな攻撃も受け付けず「ふじみのドガボン」と呼ばれている。好物はテレサで、ピューピューヒルや迷いの森のテレサを襲って食べている。
 不死身の正体は、クッパのスターのつえで心臓と体を分離しているため。体はいくら攻撃を受けてもダメージが通らず、ピューピューヒル麓の風車小屋に隠れているドガボンの心臓を直接攻撃しないと倒せない。そのため、本戦はドガボンというよりは、どちらかというとドガボンの心臓と言える。
 戦闘で心臓のHPを削ると本体と合体するが、元々のステータスが心臓よりも弱いため、結果として弱体化している。倒すと今まで食べたテレサを吐き出し、どこかへ逃げていく。元々かなり臆病な性格でテレサ達がからかっていたため、テレサ達が襲われていたのはある意味で自業自得と言える。
 漫画版では城に近づいたテレサたちが行方不明になっていたためドガボンに食べられていたと思われたが、実はテレサたちを城に招いて一緒に遊んでいただけだった。無邪気な性格であり、ゲームとは違って心臓は分離しておらずクッパの手下というわけでもない。
しょうぐんヘイホー
 ステージ４のボス。白い軍服に身を包んだヘイホー。キノコタウンの空き家にある不思議なおもちゃ箱の中に潜んでいる。ヘイホー達にいたずらをさせ、キノコタウンを混乱させていた。
 戦闘では配下のヘイホー達を戦わせるほか、自身もおもちゃの戦車に乗り込み戦う。爆弾投げや強力な電気攻撃も仕掛けてくる。負けると部下達に見捨てられ、自身も逃げていく。
ファイアパックン
 ステージ５のボス。ヨッシーアイランドのビッグパックンに似た非常に長い蔓の体をしており、全身に炎をまとっている。グツグツ火山の最深部で星の精を守っている。グツグツ火山の温度を上げようとしていたため、撃破後火山が噴火してしまう。
オズモーン
 ステージ６のボス。雲の怪物。フラワーランドの雲の上にいる。「クモクモマシーン」で強制的に雲を作り、フラワーランドを雲の楽園にしようと企んでいた。
 戦闘ではのしかかりや強力な雷攻撃を仕掛けてくる。また、ダメージを与えると受けたダメージ分の「コグモ」に分裂する。コグモも攻撃をしてくる上、コグモをオズモーンに吸い込まれると回復されてしまうため、倒すのは至難の業。また、雲であるためか電気・雷攻撃が一切通用しない。ＨＰが減ると少しずつ体積が小さくなっていく。
 漫画版では関西弁のボケキャラだったが力は本物であり、マリオたちを寄せ付けない強さを見せた。しかしルイージ、ヨッシー、ワリオが応援に駆け付けたことで形勢逆転され敗北する。1コマのみだがキャサリンも登場している（ヨッシーとデートの約束があるので迎えに来た）。
パラレラー
 ステージ７のボス。正体不明の透明人間。キノコ王国の極北にあるクリスター神殿に潜んでいる。
 戦闘ではオプションと呼ばれる氷塊を生み出しぶつけてくるほか、吹雪や分身など多彩な技を使う。強敵だが、あるバッジと仲間を用いた作戦をとると簡単に撃破する事ができ、公式攻略本にも記載されている。また、状況次第ではスターポイントが40越えという作中でもトップクラスの経験値が手に入る。
 漫画版では珍しくボケもツッコミもしない、悪役らしい悪役として描かれた。

ステージ 
本作では大きく9つのステージに分けられている。この項ではサブタイトルと共に、ステージ内の概要も示す。なお、新ステージ開始の合図（ステージ○（番号） サブタイトル）の際には助け出す星の精と、倒すべきステージボスの影が画面上に現れる。どのステージを終えても一度はキノコタウンへ戻ってくることになる。

世界の中心の街から色々なステージを冒険する構成は『イースⅢ』から着想を得ている。
 プロローグ 〜星とマリオとクリボーと…〜
 本作最初のステージ。「スターのつえ」でパワーアップしたクッパに敗れたマリオはクリボー一家に助けられ、クリオが仲間になる。途中でハンマーが入手できたり、ストーリー上初めてコワッパと戦闘になる。キノコタウンに戻り、星の精達の話を聞くまでがこのステージである。このステージでマリオは、7人の星の精を助け出してクッパを倒す決意をする。
 ステージ1 〜こうりゃく! ノコブロスのとりで〜
 キノコタウンの東に、道路をふさいでいる4人の黒いキノピオが現れる。占い師「デアール」はキノピオたちの正体はノコブロスというノコノコの集団だと見破る。ノコブロスたちはキノコ王国の東部の草原「ポカポカロード」を荒らす悪者で、そこに砦を築いて根城にしているという。正体のばれたノコブロスは砦へと逃走し、マリオ達はそれを追いかけることになった。
 ステージ2 〜アラビンいせきのなぞ〜
 星の子・ティンクがマリオの前に現れ、次の星の精はアラビン遺跡にいると教えてくれた。山を超え谷を越えてやっとたどり着いた、遺跡の建つカラカラ砂漠は、人がほとんど足を踏み入れない広大な秘境。しかも、仮に広い砂漠から遺跡のある場所を探し出せたとしても、遺跡は地中深くに埋まっていて入ることすらできないという。マリオは遺跡に入るため、オアシスの町・カラカラタウンで情報集めをすることになった。
 ステージ3 〜ふじみのドガボン〜
 ピーチ姫の伝言により、次の星の精はピューピューヒルに棲むドガボンが持っていると判明した。マリオはピューピューヒルに向かうために、キノコ王国北東の樹海・迷いの森に足を踏み入れた。怪しい森の中でマリオはセバスチャンというテレサに出会う。セバスチャンに導かれたマリオは森の中に立つ不気味な洋館に招待され、そこでテレサからドガボン退治を依頼された。洋館に住むテレサであるレサレサが言うには、ドガボンは不死身で、今まで何匹ものテレサを食べてしまったらしい。マリオは勇敢にもドガボン退治を決意し、不死身の謎を解き明かすことにした。
 ステージ4 〜とつげき! おもちゃばこ〜
 3人目の星の精を助けてキノコタウンに戻ってきたマリオは、町の異変に気付いた。住民によると、急にキノコタウン中にヘイホーが大量発生してあちこち荒らしまわっているという。そこで、マリオは機転を利かせてヘイホーの出所となっている無人家屋を探し当てた。家屋の中をさらに奥に入っていくと、大きくてカラフルな箱がひとつ置いてあった。マリオがそこに入ってみると、中には多くのヘイホーと広大なおもちゃの世界が広がっていた。
 ステージ5 〜南の海のジャンボル島〜
 次の星の精は南の島のグツグツ火山に囚われていると分かった。同じ頃、キノコタウン南の港に突如として黒い塊が出現した。その正体は腹痛を起こした鯨で、その腹を治してあげたマリオは鯨に南の島・ジャンボル島まで乗せていってもらえることになった。島に着いたマリオは原住民族であるヨッシーたちの助けを得て島の内部に広がるジャングルの奥地に分け入り、そこで島の主であるビッグキューちゃんに会う。そしてマリオはキューちゃんの力を借り、前人未到のグツグツ火山に突入した。
 ステージ6 〜花と雲につつまれて〜
 5人目の星の精を助けてキノコタウンに戻ると、キノピオハウスの前にいるリップの横にフラワーさんがおり、フラワーさんによればフラワーランドがずっと曇っているという。マリオはフラワーランドに向かい、フラワーランドを救うことになった。フラワーランドにはコボックという大木がおり、コボックによると上の雲のオズモーンが曇らせており、星の精も捕らえているという。マリオは星の精を助けるためにフラワーランドを冒険することになる。
 ステージ7 〜さいはての地へ〜
 6人目の星の精も遂に助け、残るはあと一人となる。そんな中、マリオはデアールの家を訪れると星の生まれる谷から客が来ていた。来客のハックンはマリオに是非とも訪れてほしいらしく、町にある土管からサムイサムイ村を経由して来てくださいと言い、マリオはそのとおりサムイサムイ村に行く。だが村の端にある村長の家で、マリオは倒れて動かない村長を目撃し、村長を殺したと疑われ、村から出られなくなってしまう。村長が「ゴンベエ」と書かれた紙を持っていることに気づいたマリオは、ゴンベエを民家へ連れて行く。その後村長が生きているとわかり、疑いが晴れたマリオは村長から村の外に出ることを許可される。隣の星の子達が住む星の生まれる谷でスタールからクリスター神殿へ行くよう言われ、暖かいマフラーをもらう。その後サムイサムイ村の村長から戴いたすばらしいバケツとを、村に来る途中にあった雪だるまにつけると、最後の星の精のいるクリスター神殿への道が開かれた。
 ステージ8 〜たいけつ! 大魔王クッパ〜
 7人（?）全ての星の精を救出したマリオ。星のふる丘に来ると、どこからかチョールの声と共に、キノコタウンと星の宮殿をつなぐスターロードへの道が開かれた。星の宮殿に行くと、7人の星の精がマリオを歓迎し、クッパ城行きの星の方舟を召還した。マリオ達を乗せた星の方舟は、流れ星となり、ピーチのいるクッパ城へと流れていったのだった。

主な土地 
マリオたちが冒険する舞台全体はキノコワールドと呼ばれている。

 キノコタウン
 キノコ城の城下町であり、キノコワールドで一番の都会。冒険の拠点となる場所で、様々な場所へ道や交通機関が繋がっている。ところどころに方角を案内する柱が立てられている。北部にはキノコ城が存在したが、プロローグでクッパ城に持ち上げられて大きな穴を残しており、持ち上げた際の地震により南部に積んでいた木材が散乱し、冒頭は南部に行くことができない。
 キノコタウンの地下道
 キノコタウン南部の土管からいける下水道。キノコワールド各地へ繋がり近道できる青い土管があるが、はじめからすべてを利用することはできない。ステージ4,6,8以外のステージに繋がっている。ステージ7へはここからしか行けない。
 マリオの家
 キノコタウン北西部にある土管から行くことができる。前作の『スーパーマリオRPG』とは設定が異なっているため、今作は弟のルイージも一緒に住んでいるが、今回もルイージが留守番をする。冒険の記録を調べたり、途中でルイージが家を増築してからはルイージの日記を読んだり出来る。また、ステージをクリアするごとにルイージの言動が変わる。マリオ宛ての手紙を読むこともできる。
 クリ村
 キノコタウン北西部にある、クリボー達が住む村。ただし、家を建てて定住しているのはクリオ一家だけ。ほかにあるのはキノピオハウスのみ。裏にはコワッパの遊び場がある。
 マロンロード
 クリ村とキノコタウンを結ぶ道。途中にクリキングの砦がある。
 ポカポカロード
 キノコタウン北東部に広がる道。ノコノコ村やノコブロスのとりでへはこの道を通っていく。ゲーム後半になるとゼニノコーが通せんぼするようになる。途中にはあることをするとHPを回復できる「伝説のキャンディバー」が存在する。
 ノコノコ村
 ノコノコ達が暮らす村。カメだけあって川の近くに作られている。建物の屋根が全て甲羅の型をしているのが特徴。ノコブロスから解放されたボムへい達はカメキの家に住むようになる。
 ノコブロスのとりで
 ノコノコ村の東に建っている巨大な砦。内部には複雑な仕掛けが多数ある。元々はボムへい達が住んでいた。
 ゴツゴツ山
 名前の通りゴツゴツとした岩山。汽車の駅がここにしかないので、カラカラタウンまで歩かされる。
 カラカラさばく
 ゴツゴツ山とカラカラタウンの間にある砂漠。とても広大で同じ様な面が連なっているため、道から外れるととても迷いやすい。ある場所にアラビン遺跡が隠されているほか、オアシスも存在する。
 アラビン遺跡
 砂漠に隠された遺跡。古代アラビン王国の遺跡らしい。なぜか途中の棺にはサンボマミーが入っている。カーメンはここの主を名乗っていたが、クリオ曰くアラビン遺跡はチューさんの遺跡である。チャールズ一行が後に発掘調査をしたが、大きな発見は無かったとのことである。
 カラカラタウン
 砂漠の先にある乾燥した町。今は亡きアラビン王国の国王が作ったといわれる。土造りの建物や頭にターバンを巻いた人々が印象的。町を支配するのはロレンチュ達チューさんで、キノコ族ではない。
 迷いの森
 キノコタウン東部に広がる森。4方向に道が伸びた面が多数ある。しかし、ほとんどの場合正しい場所に繋がっているのは1本のみで、誤った道に入ると入口に戻ることになる。なお、正しい道は他の道とは異なる目印を持つが、中には特別な道もある（正しい道はクリオで調べると分かる）。
 テレサのおやしきイタズラ
 迷いの森の奥にある、テレサが多く住んでいる屋敷。襲ってくることは無いが、いたずらをされる場合がある（ダメージを受ける物もある）。なお、『スーパーマリオブラザーズ』風のドット絵に変身できる壺がある。
 ピューピューヒル
 荒涼とした丘。途中にある廃墟群にはテレサが住むが、全員友好的な性格で、マリオ達に攻撃してくる事もない。また、住んでいる場所のせいか、日に焼けたような茶色い体をしている。ふもとの風車小屋にはドガボンの重要な秘密が隠されている。
 風車小屋
 ピューピューヒルにある風車小屋。入ってすぐに井戸があり、そこから地下に行ける。中は狭い。
 ドガボンの城
 全てがドガボンサイズに作られた城。中にはキャッチャンという警備員がおり、捕まると外に放り出されてしまう。ガボン達も警備をしているが、ほとんどが居眠りをしている。ドガボンを倒すと、マップでの説明が「不死身のドガボンがいる城」から「不死身だったドガボンがいた城」に変更され、廃墟となりほぼ無人の状態になる。ガボンが１人だけ残っているが、やはり居眠りをしている。
 ヘイホーのおもちゃ箱
 ヘイホー達が暮らす世界。キノコタウンの空家に隠されている。中では電車の駅に沿ってブルー、ピンク、グリーン、レッドの4つのエリアに分かれているのだが、最初は動かす電車すらなく、さらに線路がところどころで途切れているため、行けるエリアは制限されている。
 ジャンボル島
 南の海に浮かぶ島。ヨッシー村とグツグツ火山がある他は未開のジャングルが広がっている。
 ヨッシー村
 ヨッシーたちが住んでいる村。なお、BGMは『スーパーマリオ ヨッシーアイランド』（1995年、スーパーファミコン）からの流用（ファイル選択画面のBGM）である。
 ジャングル
 ピロリン草だましやギタイ草などの擬態した敵や、一工夫しなければ通れない道など仕掛けが多い。
 奥にはビッグキューちゃんの住処である巨樹が存在する。
 グツグツ火山
 熱い溶岩が噴き出す危険な火山。
 フラワーランド
 フラワーさんから合計4つのタネをもらってキノコタウンのフラワーガーデンに植えるとドアが現れ、行けるようになる。自然豊かな場所だがオズモーンに荒らされている。なぜかイバラが多い。
 雲の上
 フラワーランドで「マメのきのタネ」・「ゆたかなつち」・「おいしいみず」・「太陽の光」がそろうと豆の木が伸びていけるようになる。オズモーンがいるほか、ひとつバッジがあるだけで、他には何もない。
 サムイサムイ村
 他の地域から隔絶された極寒の地で、キノコタウン地下道の土管でのみ行ける。住民の大半はペンギンのターくん。
 サムイサムイ雪原
 サムイサムイ村の東にある雪原で、前述のノコブロスのとりでの真北にある。ここにいる雪だるまに秘密が隠されている。
 星の生まれる谷
 サムイサムイ雪原の東端で、キノコワールド最果ての地。星の子はここから天に昇るが、クッパのせいでそれができないでいる。星以外の住民は少ない。
 サムイサムイ山
 クリスターしんでんへの通り道。サムイサムイ村の村長曰く「1年に人が3人来るか来ないか」というほどの山。雪だるまの秘密を解くと行けるようになる。山というよりも神殿の城壁のようであり、特に複雑なトラップも見当たらない。
 クリスター神殿
 サムイサムイ山の頂上にある星を祭るための神殿。人々が神殿までの行き方を忘れてしまったため、「幻の神殿」とも呼ばれている。線対称な造りで、中央の鏡と絡んだ複雑な仕掛けが多い。なお、クッパの手下達がどのようにして神殿内に足を運んだかは不明。
 星の降る丘
 キノコ城の北にある、不思議な場所。常に流れ星が見える。ゲーム序盤から訪れる場所だが、終盤になって初めて重要な役割を果たす。前作の『スーパーマリオRPG』に登場した同名の場所とは異なる。
 スターロード
 星の国へ行くための道。星の精が全員集まると上ることができるようになる。星の降る丘同様、前作に同名の場所が登場するが、それとはまた異なる。
 星の国
 スターロードの先にある、星たちの住む国。古代ギリシア風のモニュメントや無限に湧き出る泉が幻想的な場所。クッパ城への渡し舟が発着する。
 クッパ城
 クッパの根城。鉄やコンクリートが剥き出しの無機質な造りで、溶岩が沸き上がる部屋や、暗い地下洞窟のような部屋もある。クッパ城というだけあって、敵も強く様々な仕掛けが随所に施されており、難易度が高い。
 キノコ城
 プロローグ序盤の舞台にして、クッパ城に持ち上げられていた冒険最後の舞台。キノピオがタンスに隠れている部屋で休むことができる。クッパを倒した後のエピローグでも登場している。

他機種版 

N64以外の共通点
 下記のN64シェーダーに対応していないため、どのバージョンでも一貫して描画されていない。
 星の国、テレサのおやしきなど特定のステージの床が変化しない。
 一部のエフェクトの挙動が、例え杖の魔法エフェクトが紫のみになっているほどオリジナル版とは異なる。
 ヘイホーの紙の積み重ねが正しく描画されていない。

Wii版
Wii版のみの仕様を挙げる
 スタート画面を開くとき、ラグが発生する。
 スーパーブロックのエネルギーボールが半透明になっていており、爆発のたびに画面が一瞬暗くなるフィルターが掛かる。
 特定の場所での処理落ちが発生しやすく、特に「ジェットふんしゃ」の処理落ちが非常に激しい。
 かいぶつの粒子が身体の外にはみ出る。
 かいぶつの攻撃波動エフェクトが白になっている。

Wii U版
Wii VC版では再現できなかったバーンエフェクトやノイズエフェクトが正しく描画される。
ここからはWii U版以降の仕様を挙げる
 太陽光が省略されている。
 一部の光エフェクトがおかしくなる。
 スーパーブロックのエネルギーボールの灰色の輪郭が目立つ。
 明度が下げられているためか爆発が発生した時のフィルターが掛からない

Wii U版のみの不具合を挙げる
 特定のシーン（ジェットふんしゃ、ドガボンが廊下を壊すときのシーン、将軍ヘイホーとの戦闘開始時）では、音飛びが発生する。
 アカリンの「ビリビリアタック」が緑色になっている。
 かいぶつの攻撃波動エフェクトが黒になっている。

NINTENDO 64 Nintendo Switch Online
NSO版のみの仕様や不具合を挙げる
 明度がオリジナル同様になった。
 クッパの火炎放射がいち早くフェードアウトされる。
 星の国に限り、床がオリジナル同様に変化する。
 スタートメニューの表示に処理落ちが発生する。
 ステージ5のボス戦に限り、フレームレートが低下する。
 かいぶつの粒子が輪郭に見られる。
それ以外の仕様はWii U版に準拠する。

脚注

外部リンク 
 公式サイト
 
 
 Nintendo Online Magazine 2000年8月号 夏休みゲーム特集

ペーパーマリオ
すとおりい
アクションRPG
2000年のコンピュータゲーム
NINTENDO64用ソフト
Wii用バーチャルコンソール対応ソフト
Wii U用バーチャルコンソール対応ソフト
NINTENDO 64 Nintendo Switch Online収録ソフト
ファミ通クロスレビューゴールド殿堂入りソフト