The story focuses on a human raised on Mars and his adaptation to, and understanding of, humans and their culture. It is set in a post-Third World War United States, where organized religions are politically powerful. There is a World Federation of Free Nations, including the demilitarized U.S., with a world government supported by Special Service troops.
A manned expedition is mounted to visit the planet Mars, but all contact is lost after landing. A second expedition 25 years later finds a single survivor, Valentine Michael Smith. Smith was born on the spacecraft and was raised entirely by the Martians. He is ordered by the Martians to accompany the returning expedition.
Because Smith is unaccustomed to the conditions on Earth, he is confined at Bethesda Hospital, where having never seen a human female, he is attended by male staff only. Seeing this restriction as a challenge, Nurse Gillian Boardman eludes the guards and goes in to see Smith. By sharing a glass of water with him, she inadvertently becomes his first female "water brother", considered a profound relationship by the Martians.
Gillian tells her lover, reporter Ben Caxton, about her experience with Smith. Ben explains that as heir to the entire exploration party, Smith is extremely wealthy, and following a legal precedent set during the colonisation of the Moon, he could be considered owner of Mars itself. His arrival on Earth has prompted a political power struggle that puts his life in danger. Ben persuades her to bug Smith's room and then publishes stories to bait the government into releasing him. Ben is seized by the government, and Gillian persuades Smith to leave the hospital with her. When government agents catch up with them, Smith makes the agents vanish, then is so shocked by Gillian's terrified reaction that he enters a semblance of catatonia. Gillian, remembering Ben's earlier suggestion, conveys Smith to Jubal Harshaw, a famous author who is also a physician and a lawyer.
Smith continues to demonstrate psychic abilities and superhuman intelligence, coupled with a childlike naïveté. When Harshaw tries to explain religion to him, Smith understands the concept of God only as "one who groks", which includes every extant organism. This leads him to express the Martian concept of life as the phrase "Thou art God", although he knows this is a bad translation. Many other human concepts such as war, clothing, and jealousy are strange to him, while the idea of an afterlife is a fact he takes for granted because Martian society is directed by "Old Ones", the spirits of Martians who have "discorporated". It is also customary for loved ones and friends to eat the bodies of the dead, in a rite similar to Holy Communion. Eventually, Harshaw arranges freedom for Smith and recognition that human law, which would have granted ownership of Mars to Smith, has no applicability to a planet already inhabited by intelligent life.
Still inexhaustibly wealthy, and now free to travel, Smith becomes a celebrity and is feted by the Earth's elite. He investigates many religions, including the Fosterite Church of the New Revelation, a populist megachurch wherein sexuality, gambling, alcohol consumption, and similar activities are allowed, even encouraged, and only considered "sinning" when not under church auspices. The Church of the New Revelation is organized in a complexity of initiatory levels: an outer circle, open to the public; a middle circle of ordinary members who support the church financially; and an inner circle of the "eternally saved" — attractive, highly sexed men and women, who serve as clergy and recruit new members. The Church owns many politicians and takes violent action against those who oppose it. Smith also has a brief career as a magician in a carnival, where he and Gillian befriend the show's tattooed lady, an "eternally saved" Fosterite named Patricia Paiwonski.
Eventually, Smith starts a Martian-influenced "Church of All Worlds" combining elements of the Fosterite cult (especially the sexual aspects) with Western esotericism, whose members learn the Martian language and thus acquire psychokinetic abilities. The church is eventually besieged by Fosterites for practicing "blasphemy", and the church building is destroyed; but unknown to the public, Smith's followers teleport to safety. Smith is arrested by the police, but escapes and returns to his followers, later explaining to Jubal that his gigantic fortune has been bequeathed to the Church. With that wealth and their new abilities, Church members will be able to re-organize human societies and cultures. Eventually, those who cannot or will not learn Smith's methods will die out, leaving Homo superior. Incidentally, this may save Earth from eventual destruction by the Martians, who were responsible for the destruction of the fifth planet, eons ago.
Smith is killed by a mob raised against him by the Fosterites. From the afterlife, he speaks briefly to grief-stricken Jubal, to dissuade him from suicide. Having consumed a small portion of Smith's remains in keeping with Martian custom, Jubal and some of the Church members return to Jubal's home to regroup and prepare for their new evangelical role founding congregations. Meanwhile, Smith re-appears in the afterlife to replace the Fosterites' eponymous founder, amid hints that Smith was an incarnation of the Archangel Michael.