冒険者である主人公（パッケージ写真では「ザッシュ」と表記）は、突如激しい地震に見舞われる。非難した先にいた老人ホワイトの話によれば、この大地震はダークキングなる邪悪な存在が地・水・火・風のクリスタルを配下の魔物たちに奪わせたことで起こったという。このままでは世界は荒廃の一途を辿る。その話を聞いたザッシュは、ダークキングを倒し世界を救う「予言の勇者」となることを決意する。

最初は土のクリスタルが眠る化石の迷宮を目指し、フォレスタに住む村娘カレンの案内で朽ちた森林を抜けようとする。しかしカレンはミノタウロスの猛毒で倒れてしまった。迷宮に挑むザッシュにトレジャーハンターを名乗る青年ロックが力を貸し、共に迷宮のボス・フレームサウルスを撃破する。目当てのお宝を手に入れたロックはパーティーから離脱した。

次に訪れた水の町アクエリアでは、水のクリスタルの暴走で町中の水が凍りついてしまっていた。このため町娘フェイの祖父ジャックは地下道に閉じ込められてしまい、フェイは水のクリスタルを魔物から取り返そうとしていた。話を聞いたザッシュも仲間に加わり、水のクリスタルが安置された氷のピラミッドへ向かう。そしてダークキングの配下アイスゴーレムを撃破する。目的を果たしたフェイはパーティーから離脱する。

次に訪れた炎の町フェイリアでは、やはり火のクリスタルの暴走によって異変に苛まれていた。町の青年レッドは、火山から帰って来ない父親の行方を心配していた。共にコンビを組んだザッシュは、火のクリスタルが安置された火山内部の溶岩ドームを目指す。火口を守っていたメデューサを倒し、続けて火のクリスタルを守っていたヒュドラも撃破する。レッドは街に残らずザッシュの冒険に付いて来たが、吊り橋で魔物に奇襲され落下して生死不明となってしまう。

入れ代わるように再びロックを加えるが、生きている樹海に阻まれて先に進むことができない。そこで森と話せるカレンの力を借りることに。フェイの家で眠っていたカレンは、うっかり地下道を爆破したフェイの爆発音で目を覚まし、ザッシュに同行する。代わりにジャックと意気投合したロックは町に残るため離脱となった。カレンの力で巨大老木との対話に成功し、木の中に巣食うモンスターを倒すことと引き換えに樹海を通り抜けることを許可された。

風の町ウィンディアでは、風のクリスタルの暴走によって強風に見舞われていた。ちょっと変わり者の老人オットー・シド・ベッケンシュタイン博士の助力を得て、パズズの塔に眠る風のクリスタルを奪還する。塔内のエレベーターを停止させ、パズズの逃げ道を封じ、見事倒すことに成功する。

全てのクリスタルの力を借りたザッシュだが、ダークキングの居場所に乗り込む手段がなかった。カレンと別れ、入れ替わるように生還したレッドを仲間に加える。そこへアクエリアの地下道に謎の船が流れ着く。それは行方不明だったカレンの父親マックの船であった。船内は魔物の巣窟となっており、ザッシュはレッドと共に魔物たちを駆逐する。船から戻るとレッドは、体調を心配したフェイによって休まされることになり、今度は彼女が仲間に加わる。メンバーチェンジはこれが最後となる。

その後、マックから船を借り受けた二人はダークキングの待つ最後の城へと乗り込む。ダークキングは、“4つのクリスタルを手中にせし者、中央の高き塔に魔界の王として君臨し、世界を思うがままに支配できる…”という伝承通りにフォーカスタワーを乗っ取り、クリスタルを手中に収めることで「伝承の魔王」として世界に君臨しようとしていた。その力はまさに絶大であったが、ザッシュとフェイの力には及ばず敗れ去り、こうして伝承の魔王は、予言の勇者によって討ち滅ぼされたのだった。

そこへあの老人ホワイトが姿を現す。実は彼の正体は、光のクリスタルが人の姿に変えたものであった。感謝されたザッシュは仲間たちの元へ戻り、カレンとの別れを得てマックの船でまだ見ぬ世界へと旅立つ。気ままな一人旅に戻ったと思いきや、いつの間にか密航していたロックが仲間に加わり、共に宛てのない航海へ出るのだった。