ストーリー

地球に帰り着いた星野鉄郎を待ち受けていたのは、機械化人とわずかに生き残った人間との血みどろの戦いだった。老パルチザンのもとで、鉄郎もまた武器をとって戦っていた。そんなある日、メーテルからのメッセージが届く。
『鉄郎、スリーナインに乗りなさい・・・』
鉄郎は再び999に乗り果てしない宇宙へと旅立った・・・昔とすっかり変わった999号は、今や完全にオート・コンピューター化され、車内には機械の身体をもつ新しいウエイトレス、メタルメナが乗っていた。
やがてたどりついた最初の停車駅があるラーメタル星。そこは、メーテルの生まれ故郷であった。鉄郎はその星でミャウダーという若者と出会い深い友情を結び、そのミャウダーから鉄郎は信じられない噂を聞く。
「メーテルこそプロメシューム。メーテルがプロメシュームの跡を継いだ」
鉄郎はラーメタル星の激戦を、キャプテン・ハーロックの空からの援護と、ミャウダーの活躍で切り抜けた鉄郎は再び駅に戻る。そして、999に乗り込もうとした時、あのメーテル再び再会する。999号を降りるように勧めるメーテルであったが、鉄郎はそれを拒んで旅を続ける事を選ぶ。
メーテルから知らされた999の目的地「大惑星雲アンドロメダ」。鉄郎はメーテルと共にそのアンドロメダに向かっていった。数々の謎を乗せ、999号は終着駅を目指し進んでゆく。そうして、「惑星プロメシューム」に到着したメーテルと鉄郎。鉄郎がその惑星で見たものは、生身の人間から命のエネルギーを抜き取る大工場であった。ベルトコンベアーで運ばれる人々の中に、ミャウダーの姿を見つけた鉄郎は怒りが頂点に達し、惑星プロメシュームを破壊しようとするのだった・・・