Setting

The City and the Stars takes place (at least) two and a half billion years from the present—ten rotations of the Galaxy since the apparition of the human species in the novel (one rotation of the Solar System around the galactic center (a galactic year) is equivalent to 220–250 million years)—in the city of Diaspar. By this time, the Earth is so old that the oceans have gone and humanity has all but left. As far as the people of Diaspar know, theirs is the only city remaining on the planet. The city of Diaspar is completely enclosed. Nobody has entered or left the city for as long as anybody can remember, and everybody in Diaspar has an instinctive insular conservatism. The story behind this fear of venturing outside the city tells of a race of ruthless invaders which beat humanity back from the stars to Earth, and then made a deal that humanity may live—if they never leave the planet.

In Diaspar, the entire city is run by the Central Computer. Not only is the city repaired by machines, but the people themselves are created by the machines as well. The computer creates bodies for the people of Diaspar to live in and stores their minds in its memory at the end of their lives. At any time, only a small number of these people are actually living in Diaspar; the rest are retained in the computer's memory banks.

All the people currently living in Diaspar have had past "lives" within Diaspar except one person—Alvin, the main character of this story. He is one of only a very small number of "Uniques", different from everybody else in Diaspar, not only because he has no past lives to remember, but because instead of fearing the outside, he feels compelled to leave. Alvin has just come to the age where he is considered grown up, and is putting all his energies to trying to find a way out. Eventually, a character named Khedron the Jester helps Alvin use the central computer to find a way out of the city of Diaspar. This involves the discovery that in the remote past, Diaspar was linked to other cities by an underground transport system. This system still exists, although its terminal is covered over and sealed, with only a secret entrance left.

Alvin's quest

Once out of Diaspar, Alvin discovers that another human habitation remains on Earth. In contrast to the technological Diaspar, Lys is a vast green oasis shielded by mountains from the worldwide desert. Its people are not stored and recreated technologically, but naturally conceive, are born, age, and die. They have rejected the hyper-advanced technology of Diaspar in favor of an almost agrarian existence, with machines used only for labor-saving purposes. The people of Lys have instead worked to perfect the arts of the mind; they are telepaths, capable of communicating with each other over great distances and without words.

Alvin continues his quest until he finds out the truth of why the people of Diaspar are so frightened of the external universe and why Lys is so scared of space travel and mechanical things. In Lys, he goes on a trip with a young man named Hilvar, who becomes his friend, and they see a signal light, which they decide to investigate. It leads them to Shalmirane, the remains of the fortress where the Invaders were fought off with unimaginable weapons, and there they encounter an extraterrestrial creature with a strange robot. The creature is the last survivor of a religious cult dating back to the days of the Galactic Empire. The robot was the companion of the founder, the "Master", who came with his followers to Earth at the end of his life. Alvin and Hilvar are unable to understand the content of the religion except that it refers to "Great Ones" who have left, but will someday return. Alvin persuades the creature to lend him the robot, arguing that the Master would want it to see how things were developing in the world. The Master had, however, forbidden the robot to give out any information at all, so Alvin does not learn anything.

Alvin instructs the robot to ignore his entreaties to take him back to Lys, knowing the people of Lys would use their great telepathic powers to induce him to return—the previous 14 Uniques had stayed. They had originally told Alvin he would be free to choose whether to stay or return, but because the people of Lys had their own insular failure, just like Diaspar, this option was no longer available. Back in Diaspar, he seeks the help of the Central Computer, which overcomes the Master's block on the robot by creating the illusion of an apocalyptic return of the Great Ones. This differs from the solution used in the original novel, which was to create a duplicate of the robot without the block.

Discoveries

Alvin learns that the Master's ship is still functional, buried outside Diaspar. He manages to retrieve it, then fetches Hilvar from Lys, and they travel into deep space. They encounter Vanamonde, a being of pure intellect, with whom Hilvar—being telepathic like other Lys people—can communicate and bring him back to Earth. From him the truth of history finally emerges.

The fearsome Invaders, it turns out, were a myth: Shalmirane was actually used to destroy the Moon to prevent it from colliding with the Earth. Diaspar and Lys are the descendants of those humans who deliberately turned away from the universe in rejection of history's greatest scientific project: the creation of a disembodied intellect. The first attempt had created a powerful but insane being, the Mad Mind. The Mad Mind had devastated the galaxy and its civilizations before being imprisoned in a "strange artificial star" called the Black Sun.

Vanamonde is the second, successful experiment of the ancient empire: a being of pure intellect, immensely old, immensely powerful, able to move instantly to any point in space—but entirely childlike and unsophisticated. Vanamonde's ultimate destiny, Hilvar realizes, is to battle the Mad Mind, when it escapes its prison at the end of time.

After this, most of the Galactic Empire had left our galaxy, leaving only a scattered few. This departure from the galaxy, leaving it to Vanamonde, was made because they had been contacted by a "very strange and very great" intelligent, extraterrestrial species, which called them urgently to the other side of the universe.

Alvin's discoveries reunite Diaspar with Lys. He then sends the ship, under the command of the robot, to search for the long-lost people of the Empire. He has no wish to join the search—even if there are human remnants in the Galaxy, they are probably decadent—and he has work to do on Earth. Even the environment, he hopes, can be revived.