Le jeune Tetsurô vit seul avec sa mère à la campagne, dans une petite maison modeste. Voulant le meilleur pour son fils, et fidèle à la promesse faite au père de l'enfant, la mère de Tetsurô décide de partir un soir pour la mégalopole en pleine tempête de neige avec l'espoir d'embarquer avec lui dans le Galaxy Express 999, le train spatial qui fait la liaison Terre-Andromède ; en effet, on raconte qu'au bout de ce voyage très coûteux, un corps mécanique peut être offert gratuitement. Alors que la mère et l'enfant progressent péniblement dans la tempête, un petit groupe d'hommes-robots, dirigé par le cruel Comte Mecha, les prend en chasse et abat la mère de Tetsurô sous les yeux de l'enfant, qu'ils laissent pour mort.

Le garçon est secouru de façon providentielle par une jeune et mystérieuse femme blonde d'une grande beauté : elle s'appelle Maetel, et offre au jeune garçon le ticket tant convoité qui l'emmènera jusqu'à Andromède, mais émet une condition : qu'il l'autorise à faire le voyage avec lui. L'enfant accepte sans hésiter, si c'est la condition pour réaliser le rêve de ses parents : devenir un homme mécanique et ainsi vivre éternellement, sans plus connaître ni la faim, ni la peur, ni la maladie... Mais avant cela, il a une mission à remplir : retrouver le Comte Mecha et ses hommes, et venger la mort de sa mère. C'est ce qu'il fait, mais loin d'éprouver du dégoût des hommes-robots, le jeune garçon continue d'espérer un jour en être un.

Maetel et Tetsurô se rendent dans la mégalopole, et tandis qu'ils attendent à l'hôtel l'heure du grand départ, des forces de sécurité font irruption et cherchent à les arrêter pour le meurtre du Comte. Maetel et l'enfant prennent la fuite, embarquent précipitemment à bord du Galaxy Express 999, et ainsi commence donc un long périple à travers l'univers, semé de pièges et d'embûches qui conduiront le jeune Tetsurô, un garçon pur et généreux, sur le sentier de la maturité, avec Maetel faisant office tout à la fois de mère, de protectrice, d'inspiratrice, de conseillère et de pédagogue. Dans sa jeunesse et sa confiance absolue, le jeune garçon ne fait pas cas de l'aura de mystère qui entoure la jeune femme. Il ne se rend pas compte qu'il cherche à accomplir un rêve qui risque bien d'en faire un jour un être aussi froid et cruel que celui qui a tué sa mère...

Un épisode typique de Ginga Tetsudô 999 se déroule presque toujours de la même manière (en manga comme à la télé d'ailleurs) : Maetel et Tetsurô font escale sur une nouvelle planète recélant maintes curiosités, mais aussi, le plus souvent, un danger contre lequel Maetel met l'enfant en garde (en restant le plus souvent vague, toutefois, et en appelant simplement à lui faire confiance). Tetsurô, curieux de tout, ne mesurant pas le danger et pensant toujours que Maetel exagère pour le préserver, n'en fait qu'à sa tête et désobéit, s'exposant alors à toutes sortes de périls, avec à chaque fois le risque de ne pas embarquer à temps à bord du Galaxy Express 999 et de se retrouver coincé pour très longtemps sur la planète en question...

Que ce soit par force, par ruse, ou en jouant de la crainte qu'elle inspire à ceux qui savent qui elle est (sans que l'enfant s'en étonne pourtant) Maetel réussira toujours à délivrer in extremis le garçon, qui tirera à chaque fois la leçon de ce qui vient de lui arriver... jusqu'à la fois suivante. Et malgré les embûches, très souvent causées par des êtres mécanisés, la détermination de Tetsurô d'en devenir un ne s'en trouve que renforcée, au désespoir semble-t-il de Maetel, dont les vraies motivations et la mission restent secrètes pendant la quasi-totalité de l'oeuvre.