The novel follows a group of eleven immortals from the ancient past to the distant future. Most of the novel follows the various immortals throughout their lives as they try to find others like themselves, avoid being killed, and remain quiet about their gift. Gradually, the immortals begin to meet across the world and form a family of sorts. After they share their secret of immortality with the rest of humanity, the ensuing years result in a human culture they no longer relate to or in which they fit. Consequently, they create and crew a starship to explore new civilizations within the galaxy.

• Neolithic, likely 3500–2800 BC — Birth of Nornagest (who is likely a reference to Norna-Gests þáttr).
• 1000 BC — Birth of Hanno, a Phoenician sailor (who might or might not be the historical Hanno the Navigator).
• 310 BC — Hanno hears that a philosopher named Pytheas is looking for a sailor to lead an expedition to locate a possible sea-route to the far North to avoid the dangers from the Gauls. Hanno meets him and agrees to head the expedition from Massalia (ancient Marseilles) to the north seas, reaching as far the country which would later be called Norway.
• 79 BC — Tu Shan is born in the Three Great Rocks district.
• 27 BC — Patulcius is born to a family of equestrian class in Rome. He takes a job in the Roman Empire's bureaucracy; when it is time for him to retire, he moves far away and simply starts his career anew with a new identity, repeating the process as needed.
• 1 AD — Hanno lives as a trader in Britannia.
• 19 AD — Tu Shan wanders from village to village in China preaching Taoist philosophy. He is approached by the Emperor of China's men who want him to serve in the emperor's court. He refuses and begins to travel westward, eventually arriving in Tibet.
• 279 AD — Hanno and Rufus' estimation of the time of Rufus' birth.
• 330 AD — Patulcius moves to Byzantium with Constantine I.
• 359 AD — Hanno (calling himself Flavius Lugo) has moved to Burdigala (Bordeaux) and become a successful merchant. During the decline of the Roman Empire he rescues and befriends Rufus. Rufus and Hanno flee Bordeaux and start to travel around Europe looking for others like themselves.
• 641 AD — Aliyat, a trader's widow from Palmyra, is forced to flee from her new husband who accuses her of witchcraft because she doesn't age. The only route for survival open to her seems to become a prostitute, a profession she is to continue across centuries and continents.
• 698 AD — Nornagest tracks down another immortal, Starkadh, a Viking warlord. He attempts to get Starkadh to join him, but Starkadh is more interested in plunder and glory. Starkadh later dies in battle.
• 998 AD — After getting baptized, Nornagest chooses to die by consciously stopping his heart.
• 1065 AD — Svoboda, like Aliyat before her, has to flee her people who question her youth. Hanno (now known as Cadoc ap Rhys) has a brief sexual encounter with Svoboda in Kiev, neither realizing the other is an immortal.
• 1068 AD — Patulcius is in Anatolia when it is conquered by the Great Seljuq Empire.
• 1072 AD — Hanno (still as Cadoc), tracks down Aliyat (now known as Athenais), who is living as a high-class courtesan in Constantinople. She betrays him as she wants no interference with her life. He is roughly rebuffed and narrowly escapes being killed.
• 1170 AD — Asagao (later named Okura) is born in Japan.
• 1237 AD - During the Mongol invasion of Kievan Rus' Svoboda (as Varvara), is living as a nun. Tartars invade Pereyaslavl and burn the monastery and nunnery outside the town. Svoboda is knocked out and raped but survived.
• 1453 AD — When the Ottoman Turks capture Constantinople, Patulcius returns to join the civil service again.
• 1540 AD — Hanno leaves a box containing a physical description of himself in a church, with instructions not to open it for a hundred years, to prove his immortality.
• 1570 AD — Tu Shan and Asagao meet in Tibet, marry and have a child who dies shortly after being born. Two years later they leave the Tibetan village and journey out into the world.
• 1640 AD — Hanno (as Jacques Lacy of Ireland), meets with Richelieu to discuss the possibility of immortals revealing their existence, a possibility the great Cardinal rejects.
• 1710 AD — The Native American named "Peregrino" (who would later take the name John Wanderer; here called Deathless) leaves his Lakota tribe.
• 1855 AD — Corinne Macandal (as Flora) escapes from slavery with the help of some friendly Quakers in Ohio.
• 1872 AD — Hanno (as Jack Tarrant) pursues John Wanderer, whom Hanno correctly believes to be also an immortal. In the pursuit Rufus is killed trying to save a settler's family from a Native American attack.
• 1908 AD — Patulcius works as a low-level bureaucrat in Turkey.
• 1925 AD — John Wanderer locates and identifies Tu Shan and Asagao. He meets with them in Tibet and speaks to them through an interpreter. At the time he is only able to hint at his true identity (as an immortal) and his belief about their identities. He proposes to return in fifty years.
• 1931 AD — Aliyat (as Clara Rosario) and Corinne (as Laurace Macandal) meet in New York City.
• 1938 AD — Hanno (as David McCready) meets Patulcius (as Oktay Saygun), having located him by placing an advertisement written by John Wanderer which reads, "Those who have lived so long that our forefathers are like brothers and comrades to them." Patulcius admits to Hanno that he is an immortal and agrees to keep in touch but makes it clear that he likes his life and doesn't want to join up with Hanno.
• 1942 AD — Svoboda takes part in World War II skirmishes around Stalingrad.
• 1975 AD — John Wanderer makes good on his promise and returns to Tu Shan and Asagao. Tu Shan and Asagao reveal that their children are all mortal despite the fact that they have two immortal parents. Wanderer convinces them to join him and Hanno in America. Hanno has been placing ads asking other immortals to join him. He has also founded a research team to find out how to grant immortality to everyone.
• In the future, everyone is immortal, and the Immortals have long ago revealed themselves. There is no civil service, so Patulcius is no longer employable. Tu Shan has tried to return to a primitive life and failed, as there is no longer a market for his handicrafts. They, mostly Hanno, convince the government to build them a ship with which to explore the universe.
• (some time later) They are on a near light speed ship to find other intelligent life. During the voyage, Hanno goes against the wishes of the crew and turns the ship in another direction. He spends an unspecified amount of time being ostracized by them for this.

As their name implies, at a certain point Immortals stop outwardly aging, generally at about twenty-five years, though apparently among East Asians possibly a little later. When the Immortals' teeth are damaged, they regrow. Immortals receive no permanent scars and also never contract contagious illnesses, even during times of plague. They remain fertile for as long as they live and can rapidly heal broken bones or other serious wounds. If the Immortal men are circumcised, their foreskins will regenerate. Speculation on "recurrent intactness" among women is left unanswered, with the possibility of the female hymen likewise restoring itself having been brought up at one point during dialogue in the novel. Immortals can and in the course of the novel do die, as they are not capable of recovering from injuries such as a stab to the heart or decapitation. There is also discussion about whether long-term exposure to tobacco smoke might present the possibility of lung cancer developing, though the researcher who opens the possibility admits he has no data on the matter.

• Chapter 3, "The Comrade," was originally printed in Analog Science Fiction/Science Fact in June 1988.

• The Boat of a Million Years title listing at the Internet Speculative Fiction Database
• The Boat of a Million Years at Worlds Without End