遠い未来。
地球温暖化の進行により多くの島嶼国家が海へ沈んだ。かつてオセアニアに存在した国々の人々は、現在では巨大な洋上都市を築き、海の上で暮らしている。

主人公・カイは、洋上国家カヌヴェアに暮らす少年だ。彼のアルバイトは、飛行艇で海面に鉄粉を撒くこと。鉄粉を撒くことで藻類を大量発生させ、大量のCO₂を吸収させる。それがカヌヴェアが掲げる“温暖化逆転計画”であった。

しかしこの計画には裏の顔がある。
カヌヴェアは、藻の異常繁殖による海洋生態系の破壊も顧みず、沈んだ故郷の島々を取り戻すと信じて突き進む過激な環境テロ国家と化していた。

ある日、作業中のカイは海に浮かぶ一人の少女を発見する。助け上げてみると、その少女は行方不明になっていたカヌヴェアの女王ミレイだった。なんとカイと同じ年頃である。
ミレイは、自分の人気と権威を利用して強硬な政策を進める宰相に反発していた。海を傷つけたくないという思いを押し殺し続けることに耐えられず、城を抜け出してきたのだ。

こうして二人の逃避行が始まる。
宰相が差し向けた追手、そして女王を捕らえて身代金を得ようとする海賊たちが、彼らを執拗に追い回す。

やがて二人は海賊に捕らえられ、船で働かされることになる。ところが、その海賊船もまた宰相の軍に追われる。混乱の中、カイとミレイ、そして海賊たちは追撃をかわしながら洋上を逃れ続けた。

長い逃亡の果て、彼らは沈んだカヌヴェアの島々が眠る海域へと辿り着く。二人は潜水服を着て海中を探索する。初めて訪れたはずなのに、どこか懐かしさを覚える光景が広がっていた。

しかしその場所にも、ついに宰相の軍勢が迫る。
逃げ場を失った中、カイは勇気を振り絞り、宰相と直接対峙する。激しい戦いの末、ついに宰相を打ち倒す。

混乱が収まった後、ミレイは軍艦へと戻り、初めて“自らの意志”で国を導く覚悟を示す。
そして宣言する。

「これからは、もっと穏健な手段で海を守っていく」