„Gaia und Terra
zwei Planeten, ein Schicksal
einer der Planet der Zerstörung - Terra
der Andere der Planet des Lebens - Gaia
im ewigen Streit um das Leben
bis zur Zerstörung
Friedlich Handeltreibend
vergessen durch die Zeit
Streiten sie trotz Zerstörung Terras weiter
bis auch der letzte Hinweis Terras getilgt wurde.“
Zwanzig Jahre sind nun vergangen, seit Zidane, Garnet und ihre Freunde den Nebel und somit auch die Nebelmonster vom Planeten Gaia vertrieben haben. Und dennoch gibt es nachwievor Orte, an denen plötzlich Nebel erscheint und nur Tote zurücklässt. Niemand weiß, was es mit diesem Nebel auf sich hat und dennoch weiß jeder, dass ihnen die Zeit davon rennt, bis der Nebel sich erneut auf dem ganzen Planeten ausbreitet.
Claude ist ein normaler Söldner, der sein Leben in Treno, der Vergnügungsstadt des Reiches Alexandria, fristet. Auf der Suche nach einem Weg den Kontinent zu verlassen, findet er ein völlig schwarzes Luftschiff, welches ihn seltsamerweise an etwas erinnert. Bevor er sich jedoch an die Mannschaft des Schiffs wenden kann, fällt ein Fass von diesem. Es stellt sich heraus, dass sich darin das Mädchen Daiya befindet, welche wohl eine Gefangene auf diesem ist. In Eile heuert sie Claude als Beschützer an, woraufhin sie die Stadt verlassen. Da Daiya jedoch die Menschen vom schwarzen Luftschiff verfolgen will, bleibt ihnen nichts anderes übrig als ein anderes Luftschiff zu finden. Mit Hilfe von Eiko, der Tochter des Herzogs von Lindblum, schaffen sie es sich ein Luftschiff zu leihen und verfolgen daraufhin die Männer in Schwarz. Allerdings muss die ungleiche Gruppe sehr schnell feststellen, dass sich hinter dieser Gruppe mehr versteckt, als nur eine harmlose Sekte.
