近頃噂になっている男・クラウドの調査をせよとのルード総督の命を受け、航海士ニコルソンは嵐の中海に向かう。そこで出会った元海賊のクラウドは、大砲の威力で嵐を消し去る「ストームクリーン」という技術で、嵐の中の船を助け、報酬を得ていた。クラウドはこの技術を武器に海軍へ協力を申し出る。快く承諾したルード総督だったが、そこには「海賊」に対する深い憎悪が隠されていたのだ。

5年前、クラウドは恋人・セイラの父親に会うため、セイラと共に海に出航したが、「デビルストーム」という大嵐によって、セイラを含む仲間をすべて失っていた。海に眠るセイラのため、世界中の嵐を消し去りたいと願うクラウドは、海軍との連携によって次々と嵐を消し去っていく。

やがてルード総督は、クラウドの技術を受け継ぐと、クラウド達を捕らえてしまう。
ルード総督は、5年前「デビルストーム」に巻き込まれて亡くなったセイラの父親であり、その原因は海賊にあると信じていた。海賊に対して深い憎悪をつのらせるルード総督だったが、クラウドの技術を手に入れるために、クラウドに協力していたように見せかけていたのだった。

そんなとき、またもや海に「デビルストーム」発生の予兆が現れ始める。
「デビルストーム」を消し去るには天才的な航海技術と、相当数の強力な爆弾が必要であり、その爆弾を使用すれば、自身の船すら破壊してしまうことがわかる。「ストームクリーン」の技術を手に入れた海軍ではあったが、「デビルストーム」を前にしてどうすることもできなかった。

しかし、クラウドは「デビルストーム」を消し去るため、そして街を守るため、一人海へ向かっていく。