なお、物語の詳細や新編の内容についてはお答えしかねます。各自でコミックを読んでください。

　西暦２２２１年。地球の宇宙交通網は飛躍的進歩を遂げていた。各惑星間には宇宙列車が走り、人類は太陽系外へと進出していた。また、科学は衰えることのない肉体、すなわち動物体の機械化に成功していた。機械化された人間は永遠の生命を持ち、生身の人間を狩猟の対象として虫けらのように殺しまわっていた。少年星野鉄郎の母、星野加奈恵も機械伯爵によって殺された。鉄郎は機械化人間への復讐のために、また母親との約束のため、機械の体をただでくれるという星へ行く、銀河鉄道９９９に乗るため、メガロポリス中央ステーションへ向かう。しかし吹雪の中鉄郎は倒れてしまう。鉄郎は、謎の女性メーテルによって救われる。彼女はもし一緒に連れていってくれるなら、高額な９９９の無期限定期券をただであげるという。そうして鉄郎はメーテルと共に旅することとなる。機械伯爵を殺した鉄郎は機械ポリスに追われる身となる。逃げ出すように二人は９９９へ乗り込む。

　鉄郎を乗せた９９９は、終着アンドロメダまでに、様々な星へと停車する。この星々に鉄郎は立ち寄り、ときに危険な状態に陥りながらも、これをなんとか切り抜ける。また、多くの人と出会う。そして彼らと友となり、別れていく。ガラスのクレア、大盗賊アンタレス、女海賊エメラルダス、宇宙海賊ハーロック、男の中の男サケザン…。彼らとの出会いは鉄郎を大人へ、そして一人前の男へと導いていく。