British adventurer Richard Francis Burton dies on Earth and is revived in mid-air in a vast dark room filled with human bodies, some only half formed. There, he is confronted by men in a flying vehicle who then blast him with a weapon.
He next awakes upon the shores of a mysterious river, naked and hairless. All around him are other people in a similar situation. Shortly after they awaken, a nearby structure, nicknamed a "grailstone," causes food and other supplies to appear in the "grails" bound to each individual. Burton quickly attracts a group of companions: the neanderthal Kazzintuitruaabemss (nicknamed Kazz), the science fiction author Peter Jairus Frigate, and Alice Liddell. Among these is the extraterrestrial Monat Grrautut, earlier part of a small group of beings from Tau Ceti who had arrived on Earth in the early 21st century. When one of their number was accidentally killed by humans, their spaceship automatically killed most of the people on Earth. Frigate and others alive at the time confirm Monat's story. Retreating into the nearby woods for safety, Burton's party chew gum provided by their grails, and discover that this gum is a powerful hallucinogen. As days and weeks pass, people's physical wants are provided for by the grails, which eventually produce a set of cloths used for clothing. Rumors reach Burton's region that the river continues seemingly forever. One night, Burton is visited by a mysterious cloaked figure, whom Burton dubs "The Mysterious Stranger," who explains that he is one of the beings who has constructed this world and resurrected humanity on its shores, and tells Burton to approach the headwaters of the river.
After setting off, Burton's group encounters many adventures; but are enslaved by a riverbank kingdom run by Tullus Hostilius and Hermann Göring, against whom Burton leads a successful revolt. Göring himself is killed by Alice. After the revolt Burton is part of the nation's ruling council. Later, the protagonists discover a person among them whom they conclude is an agent of the beings who created this world. Before the man can be questioned, he dies of no apparent cause. An autopsy reveals a small device planted in the man's brain which apparently allowed him to kill himself at will. Burton is visited by the Mysterious Stranger and is warned that the beings who created this world, to whom the Stranger refers as "Ethicals", are close to capturing Burton. Desperate to escape, Burton kills himself to be resurrected elsewhere in the river valley, and continues thus to explore it. He often finds himself resurrected near Hermann Göring, who undergoes a moral and religious conversion and joins the pacifist Church of the Second Chance. After many resurrections, Burton finds himself resurrected not in the river but in the Dark Tower at the headwaters, and is interrogated by a council of Ethicals to discover the identity of Burton's "Mysterious Stranger". After fruitlessly questioning him, the Ethicals inform him that they will return him to the river valley, remembering nothing of themselves, and restore him to his friends; but the Mysterious Stranger prevents them from removing his memory and Burton resolves to continue pursuing the truth about the Ethicals and their intentions for the Riverworld.