The story is told through the narrative of Sparrow, a 17-year-old technician aboard the Astron, which is a multigenerational starship sent from Earth on a search for life on other planets throughout the Milky Way. Sparrow fell off a cliff during one planetside excursion and is stricken with amnesia. No one will discuss his past with him and the computer has restricted his data, reasoning that he should "look within" to fully recover. Sparrow struggles to revive his memory and familiarizes himself with the Astron, the crew, the enigmatic Captain Kusaka, the state of the ship and its mission; in which the search for extraterrestrial life has lasted over 2,000 years with no success.

The ship has slowly shrunk from the crew cannibalizing sealed-off sections for parts and breaking apart from centuries of wear; meanwhile, the crew has dwindled from generations of selective breeding. The Captain wants to take the Astron to a section of the galaxy where stars are more numerous and older where planets are more likely to harbor life, but to do so they would have to cross the empty space between spiral arms they call "the Dark". Most members of the crew know that they will not survive the journey since it would take several centuries to cross and the ship would not make it with its current rate of attrition of their closed ecological system. But Captain Kusaka, who is immortal and obsessed with exploration, does not heed to the warnings and will do whatever it takes to complete the mission. As a result, the crew secretly try to plan a mutiny to seize control of the ship and return to Earth, the only place they know that harbors life.

Sparrow refuses to join the mutiny with his friends against Kusaka, but is torn since he knows they won't survive the trip and that chances of finding life are almost nonexistent, thus making the mission futile but the Captain won't accept it. Things change when Sparrow slowly discovers that he is also immortal like the Captain, and that he has lived previous "lives" on the ship as the same man but with different names and his memories of every previous identity are erased every generation by orders of the Captain. He learns that he originally volunteered for the role to be the mirror for every crew to "remember what its like to be human"; since they've been isolated from the rest of humanity over the centuries the crew has formed their own collective-mind culture that's overly benign and incapable of harm since they regard life as the most precious thing in existence (also makes them reluctant to mutiny). Sparrow also learns that he was the first mutineer and Kusaka erased his memories to keep the crew in line and Sparrow from seizing control of the ship since the Astron's central computer only responds to the minds of the immortal crew members, and should they be removed the ship would not function and would drift through space forever.

When they leave the last star system explored to enter "the Dark", Captain Kusaka tries to suppress the conspirators even though they are benign, but Sparrow gives them the resolution to fight when they realize that since the ship has traveled so far through relativistic time dilation, human civilization on Earth may have ceased to exist and that they may be the only known lifeforms left in the universe. Moreover, since the governments that sent them out no longer exist, Kusaka is no longer lawfully in command. In a last-ditch attempt at mutiny, most of the crew get on shuttles and landers and leave the ship, preferring to die quickly in space than to venture into "the Dark" with Kusaka. Meanwhile, before the mutineers' life support fails, Sparrow fights Kusaka alone in a hidden room that holds the preserved remains of the original first generation crew. This triggers all of Sparrow's memories and past personalities to surface at once in a dissociative identity breakdown, which leads to the resurfacing of his original identity: Raymond Stone, who was the return trip Captain. In the ensuing fight, Raymond fatally wounds Kusaka.

With the mutiny over, Raymond takes command of the Astron and sets a course back to Earth, which takes 20 generations (400 years) to reach. During that time, Raymond watches the crew he has known age and die and recycled for mass and minerals on the ship as well as their descendant crews come and go, thus making him realize the value of life and the price of immortality.

The story ends when the Astron, after 2500 ship-years (or approximately 17,000 time-dilated Julian years as calculated earlier), finally returns to an uninhabited Earth for the descendants of the original crew and Raymond to repopulate. While they are celebrating, they are shocked to discover an alien ship has also found Earth.