"Tin Soldier" tells the story of Maris—an ex-soldier who, following wounds sustained in battle, has received cybernetic implants that, as a side effect, slow his aging to "about five years for every hundred" (he is 115 years old as the story begins, though physically he looks "about twenty-five")—and the story of Brandy (short for Branduin), a female starship crew member.

Maris has started a bar named "Tin Soldier" in the spaceport town of New Piraeus. None of his customers know his real name and call him "Tin Soldier"—or "Soldier" for short—after his bar.

Only women are allowed to crew starships, since male bodies cannot handle the stresses of space travel. Since trips between star systems require decades (while the female crew do not age due to relativistic effects), Soldier does a brisk business among starship crews because, apparently never ageing, he is the only familiar face they can see, decade after decade, whenever they come into port.

Brandy is "maybe eighteen" and assigned to her ship which only visits Soldier's planet every 25 years, when she first meets Soldier. Because of the relativistic effects of space travel, she only ages a few years between visits, while Soldier ages even less.

The novella follows the relationship that develops between two people who fall in love, but through circumstances can only see each other for a few days every 25 years.

As the author said in the introduction to "Tin Soldier" published in the 1979 Vinge collection Eyes of Amber and Other Stories:

"Tin Soldier" was the first story I ever seriously sat down to write... Although it was my first story, it seems to be the one a lot of readers like the best. (I may wind up someday feeling like Isaac Asimov, who complains that after all these years, people still like his first story best – everything has been downhill ever since.)^[2]

According to Joan Vinge, "Tin Soldier" had two primary inspirations. The first was the song "Brandy (You're a Fine Girl)" by the band Looking Glass, which had been a Billboard Hot 100 #1 hit in 1972, shortly before Vinge wrote the story. The second, as the title suggests, was Hans Christian Andersen's short story "The Steadfast Tin Soldier" and its tale of a crippled toy soldier who falls in love with a paper ballerina.

Vinge commented:

...this is [a] story that had its roots in song – in this case a song called "Brandy," which was about a woman waiting for her man to return from the sea; always knowing, and accepting, that the sea would always come first for him. I had remarked to [her husband] Vernor that a similar kind of story set in space would have terrific potential for descriptions of the beauty of deep space. He made the suggestion that it ought to be the woman who went into space, the man who stayed behind... The story grew from there, and somewhere in the planning stages, I noticed the parallels between my story as it was developing, and the Andersen fairy tale "The Steadfast Tin Soldier." ...so I decided to make use of the symbolic aspects of the Andersen story within the framework of my own. Recently I became aware of another uncanny parallel to this story – George R. R. Martin has written a story which was also inspired by the song "Brandy," and also involves a woman who goes into space and a man who stays behind. Much to our mutual relief, the resemblances end there, and the basic stories are very different.^[3]

The George R. R. Martin story also inspired by "Brandy" is "Fast-Friend" and was collected in Sandkings.