遥か昔、とある惑星に高度な文明を築いた「ゼノ・パレス」は、自らの科学力の発展によって母なる星を滅ぼしてしまった。生き延びるため、彼らは宇宙への脱出を決意する。自らの遺伝情報を巨大移民船「エストーリオ」に封印し、選ばれた軍人たちが船の運航や移住先の探索を担う一方、他の民は彼らに未来を託して永い眠りについた。
やがてエストーリオは、新たな移住先として「約束の星・テーラ」――すなわち地球を発見する。しかし、そこにはすでに初期文明を築いた人類が存在していた。この事実をめぐり、ゼノ・パレス内部は二派に分かれる。人類を排除して速やかに移住を果たそうとする強硬派〈マーズ〉と、長い年月をかけて人類と共存の道を探ろうとする穏健派〈オシリス〉である。
対立はやがてエストーリオ内部での内戦へと発展し、戦闘に長けた強硬派が優勢となる。穏健派は最後の手段として、「ゼノンズ・ガーディアン」と呼ばれる三体の戦闘ロボットと、それを格納する三隻の戦艦をテーラへと送り出した。彼らはこの機体を地球の原住民に託し、いずれ訪れるであろう強硬派との戦いに備えさせようとしたのである。
三隻の戦艦は地球に到達し、江戸時代の日本――蝦夷地（のちの北海道）、江戸（のちの東京）、薩摩国（のちの鹿児島県）――にそれぞれ落下した。現地の人々はその巨大な遺産兵器を地中深くに封印し、古文書などを通して後世へとその存在を伝えた。
そして時は流れて現代。エストーリオはついに地球軌道へと到達し、ゼノ・パレスは日本列島を足がかりに地球侵略を開始する。それに呼応するように、北海道・東京・鹿児島の地下に眠っていた遺産兵器が目覚め、人類とゼノ・パレスの壮絶な戦いが幕を開けた。
