Foundation and Earth is the story of one man's quest to justify a decision he's already made. The story begins with Golan Trevize asking why he had decided that all of humankind should become part of Gaia. Gaia is a planet of a single consciousness, a single super organism, in a sense. Trevize gradually explains that he has made that decision while discarding the idea of another plan, one that is never explained. That plan, devised by Hari Seldon, depends on two fundamental truths - that there be sufficient numbers of people involved so that statistical data can be projected, and that the people not be aware of the plan's projected outcomes.

Trevize believes there is something missing and believes the answer lies on Earth. It's not until he reaches the Earth's moon that Trevize decides that becoming a single organism is the best answer because Seldon's Plan doesn't take into account that intelligent life from other galaxies could interfere with humans, even causing a war and self-destruction. He reasons that if all are part of the greater consciousness, all will be interested only in what is best for the greater good. When he reaches that destination, he also discovers that the robot, Daneel, has played a role in his travels, guiding him to that location because Daneel is "dying." Daneel tells Trevize that it was actually the robots, including Daneel, who created several of the worlds and societies, including Gaia.

Trevize's traveling companion is a scholar - Pelorat - who is knowledgeable in the myths surrounding the existence of Earth. Pelorat met a Gaian named Bliss and the two become physically and emotionally involved. The three set off in search of Earth and the answers Trevize seeks. They travel to a series of locations, each with the hope of finding information that will offer the location of Earth. They encounter strange planets, such as Comporellon, where they are detained because the government wants their ship. Trevize convinces the transportation minister to allow them to leave. The minister allows it because she is superstitious about Earth and believes anyone on a quest for its location is likely to bring down the wrath of "He" who punishes. They visit Aurora, a planet with no humans but with ruins of buildings that yield up a clue. They are chased from the planet by a pack of wild dogs. They visit Solaria, a planet peopled with only twelve hundred humans, all living in solitude. Each has special powers that allow them to conduct energy that powers the robots that take care of his daily needs. They meet Bander the hermaphrodite who talks to them at first then informs them that in plans to kill them. Bliss tries to stop him and inadvertently kills it. As they are escaping, they discover that Bander has a child. They also learn that the child is too young to take over Bander's escape and take Fallom with them as they escape the guardian robots.

Their next stop is the uninhabited Melpomenia where they find additional clues to the location of Earth and are immediately inundated with moss that grows very quickly in the presence of their carbon-base. They next reach Alpha with its one island, called New Earth. The entire planet is water but for that one stretch of land. The people seem friendly and Trevize has sex with a beautiful woman named Hiroko. Fallom knows how to play the flute and mesmerizes the people with her talent. Then Hiroko tells Trevize that she has infected him with a deadly but inactive virus and that it will be activated once the men of the planet return from fishing. Trevize and the others escape during the night. Finally, they find Earth only to find that their fears had been confirmed and the planet was radioactive. No life could survive there and Trevize spends some time trying to decide what to do. It's actually Fallom who tries to take control of the ship in order to return to her home planet that brings Trevize's attention to the moon. Once there, they discover the twenty-thousand-year-old robot Daneel who tells that he was responsible for establishing Solaria, New Earth and Gaia. After talking with Daneel, Trevize finds that he is ready to commit mankind's fate to Gaia. Daneel reveals that he is "dying" and that he needs to meld with a human brain in order to extend his own life and continue his work. He wants Fellom.

The book ends with Trevize, Pelorat and Bliss still on the moon and apparently ready to move on to the next phase of the development of Galaxia, a Galaxy-wide unitary organism consisting of all sentient creatures. The final sentence of the book is perhaps a tease of what's to come in the next installment. Trevize says that he feels a "sudden twinge of trouble," and tries to dismiss it, saying that there's no enemy "already here and among us." The final sentence reads, "And he did not look down to the meet the brooding eyes of Fallom - hermaphroditic, transductive, different - as they rested, unfathomable, on him."