The story's protagonist is Poilar Crookleg, member of a humanoid race with a pastoral civilization at a level roughly corresponding to that of the Iron Age of human civilization. Only as the story develops it becomes apparent that these people are not humans; their hands have an additional opposing thumb, and they have limited shapeshifting abilities which allows them to loosen their joints, to adapt their skin and inner organs to environmental changes, and to extrude suction cups for climbing. Shapeshifting is also an intrinsic part of their sexuality, for in the absence of sexual arousal both sexes maintain a neuter form without overt gender characteristics. The planet is located in a binary star system where it seems to be in orbit around the major white and luminous component, Ekmelios (probably an F-type star) while reddish Marilemma (apparently an M-type red dwarf) is much more distant.

Poilar is a youngster in his village, Jespodar, which is situated at the rim of a lowland (extremely hot and humid with a very dense atmosphere by earthly standards, as can be deduced) immediately at the foothills of The Wall, a huge mountain range complex that rises to an unseen summit. The peoples' religion revolves around The Wall since thousands of planet-years ago the semi-mythical First Climber ascended to the summit where he met The Gods who introduced him to the basics of civilization. From this time onward, the people of Jespodar (as well as those of numerous other villages) pledged themselves to an annual pilgrimage of twenty men and twenty women who are supposed to re-enact the First Climber's achievement. The selection mechanisms for those aspiring to the pilgrimage are rigid and the three-year training is extremely challenging both physically and mentally. Each team of forty pilgrims that sets out for The Wall is the best the community can muster, according to general belief, but some pilgrims speculate that the selection process may include other motivations. However, for times unknown only a very few stragglers have returned to Jespodar at irregular intervals and these Returned Ones are mentally disturbed or in any case would not tell coherent stories of their experiences on The Wall. All that can be deduced is that on the various levels and segments of the huge mountain range there are distinct domains (the "kingdoms") populated by beings of variegated and extreme strangeness. Although nothing useful has been brought back from The Wall for times beyond remembrance, the annual pilgrimages continue with religious fervor.

Poilar, whose father and grandfather had been pilgrims who never returned, is also pledged to The Wall. Together with his friend Traiben, a penetrating intellectual and skeptic, he is selected for the pilgrim group as he reaches the proper age. When they set out for The Wall, Poilar is elected leader of his Forty. As the pilgrims ascend they find that the fabled kingdoms are dwellings of former pilgrims who, by account of their various character flaws, have abandoned their pledge for the summit and have succumbed to one or the other specific enticement created by the "Change-Fire" forces emanating from the mountain. These stimulate and de-regulate their shapeshifter ability, turning their victims into grossly distorted beings - "Transformed Ones." Each domain the pilgrim band traverses teaches them a personal lesson.

As the pilgrims approach the last third of their journey they meet a totally exhausted alien being who - for all the strange set of his bodily frame, the fact that he has only one thumb on each five-fingered hand, and permanently extruded male genitals - does not seem to be a Transformed One. Speaking through a small translator box, he reveals that he has descended from the summit to reconnoiter; now he is in no physical shape to return to his colleagues, who in turn cannot retrieve him because of unspecified problems at the summit. When asked whether he has seen the gods who are supposed to reside there, the Earthman becomes very evasive. The human alien soon dies, and because Poilar had given his solemn promise to take him to the summit he orders the corpse to be eviscerated and preserved so that it can be carried onward. As the band proceeds, its members dwindle away fast.

Immediately below the cloud sheath veiling the summit, Poilar and his tattered and decimated team stumble upon an Arcadia-like domain whose inhabitants are not transformed but ageless - they have discovered a Fountain of Youth. The local king turns out to be Poilar's grandfather who begs him not to proceed to the summit because there is only grief to be found there. He reveals that his own son (Poilar's father) did not heed this advice, and together with all his surviving companions had sought obliteration in the Fountain of Youth on the return trip. Indeed, the kingdoms on the highest level of the mountain seem to be populated mostly by those who had been to the summit.

Nevertheless, Poilar takes the remainder of his team to the summit plateau, where the pilgrims break through the clouds to arrive under a strange sky (blue instead of the accustomed white), totally exhausted from physical exertion in what for them is air of unbearable coldness and almost too thin to support respiration, in spite of all shapeshifter adjustments they are capable of. Having achieved the sworn objective of their lives, they are utterly shattered by what they see: no palaces with gods blissfully ambling around, but a horde of ape-like savage creatures laying siege to three Earthmen in a small spaceship. The decayed ruins of another, much larger and very old, spaceship hull can be seen in the distance.

In their despair and disgust, Poilar and his pilgrims decide to purge the summit; they throw every single one of the debased creatures into the abyss. The besieged humans then emerge from their spaceship and relate, in terms that Poilar and his people can comprehend, that they are a survey team from Earth that is charged with checking the status of human colonies with which contact has been lost. The members of the colony that had been established on the summit of The Wall (the only place on the planet where conditions seemed Earth-like) had been the gods whom the First Climber had met. Apparently, over the many generations since the First Climber had encountered the colony, the humans had degenerated under the radiation of the planet's sun and the emanations from the mountain range to become the ape-like creatures Poilar's team has slaughtered.

Having assured the pilgrims that no Earthmen would ever intrude on them again, the patrol ship takes off. Poilar and his team return to his village and relate the truth about their "gods" to their people, thereby ending all pilgrimages and putting their race on a new track of civilization that could ultimately make them into something like their gods of old: "It will be our task to build wagons to carry us between villages, and then sky-wagons, and then star-wagons, and then we will meet the gods again; but this time it will be as equals."

• Silverberg, R. Kingdoms of the Wall. Bantam Spectra Books, 1993. ISBN 0-553-56544-3