オリンポスから少しズレた場所に到着したソラたちは、ハートレスに女の人が襲われているのを目撃する。
それはヘラクレスの友達、メガラだった。
ヘラクレスを休ませるよう、ハデスに頼みに行きたいという。ソラたちは彼女を心配し、代わりに冥界へ向かうことに。

そのころハデスは、冥界から呼び出した戦士アーロンをヘラクレスと戦わせようとしていた。
だがアーロンはそれを断る。
やってきたソラたちはアーロンを手伝い、ハデスと戦うが、冥界では、呪いにより力が出ない。
苦戦の末、追っ手のケルベロスを封じ、なんとか冥界を脱出した。

そのころハデスは、ソラのキーブレードを利用して、冥界のコロシアムの封印を解こうとしていた------

ソラたちはやってきたコロシアムでヘラクレスと再会する。
「ハデスをこらしめたい」と相談すると、ヘラクレスが冥界の呪いを防ぐオリンポス・ストーンを取りに行ってくれることになった。
その間、ソラたちはフィルのもとでトレーニングをすることに。

ところが戻ってきたヘラクレスは浮かない顔だった。
オリンポス・ストーンが黒い服の人物に盗まれたというのだ。そこへハデスが現れて、メガラを冥界に引き込んだという。
すぐにでも助けに行きたいヘラクレスだったが、ヒュドラと対戦しなければならない。
一方フィルも黒い服の人物に襲われていた。事件を解決できるのはソラたちしかいない。

呪いに苦しみつつ、冥界の奥へ突き進んでゆく。
発見したXIII機関のメンバーを倒し、オリンポス・ストーンを取り戻す。これで冥界の呪いも怖くない。
そして奥にあった怪しげな封印をキーブレードで解くと------そこには捕われのメガラが!
だが、ハデスはなぜか嬉しそうにその場を立ち去る。

駆けつけたヘラクレスが敵をひきつけている間に、メガラを地上へ連れ帰ろうとするが、彼女はヘラクレスの身を心配する。
助けに戻ったソラたちは、ハデスに手を貸していたピートを倒す。
だが、ハデスが不吉な言葉を残す。
「オリンポスに帰らなくていいのか? 」

ヘラクレスが倒したはずのヒュドラが復活し、コロシアムが破壊されていた。
ヒュドラを倒すが、ヘラクレスはすっかり気を落としてしまう。
心配ではあるが、彼のことはメガラにまかせておくしかないようだ。


冥界入口に、得体の知れない巨大なものが現れた。
神々の王ゼウスにより封印されていたはずの冥界コロシアムが、封印を解かれ復活したのだという。
ハデスが開催するハデスカップにソラたちやヘラクレスも出場することに。

決勝まで勝ち進めば、アーロンと戦えるかもしれない。
ヘラクレスは自信を取り戻していないが、順調に戦いを勝ち進んでいくソラたち。
ついに決勝進出を決める!
ところが試合後に出会ったアーロンの様子がおかしい。
ヘラクレスやソラたちを始末したいハデスが、小さな人形を取り返せばアーロンの心も戻ってくるはずだ。
ヘラクレス対アーロンの決勝戦が始まる中、ソラたちは冥界に向かう。

やがて見つけた人形には、アーロンのつらい過去がつまっていた。
そうやって苦しんだからこそ、彼は強い心を身につけたのだろう------
ソラたちの活躍でアーロンは心を取り戻し、メガラへの想いにより、ヘラクレスは復活した!
みんなは力を合わせ、ハデスを倒す。

夜空には英雄の証である星座が輝いていた。