Dorothea "Dodo" Chaplet has always dreamed of travelling, but her mother's death and her father's subsequent breakdown and hospitalisation have put paid to those dreams. Sent to stay with an uncaring great-aunt in London, she occasionally helps an elderly neighbour with his shopping and house care -- but one day she arrives at his home to find that he's been killed by an alien who has taken his form. The alien keeps Dodo hostage in the house to prevent her from alerting others to its presence. Dodo speaks to it, trying to convince it to let her go, and learns that it killed the old man in self-defense when the frightened old man attacked it. As she spends time with the alien it seems to shape its personality based on her feelings and thoughts, and eventually it names itself Joseph, an unthreatening name. But Joseph is still learning about the planet he's found himself on, and while trying to show affection to his new friend he attempts to rape her. Fortunately he is incapacitated by a psychic scream which only he can hear, and Dodo is able to escape. She seeks help in a nearby police box on the Common, but when she enters she finds that it's not a police box at all. Terrified that she's stumbled upon Joseph's ship, she blurts out the first thing that comes into her head when the old man inside demands to know what she's doing there. The old man's friend Steven returns to warn him that the police are approaching, and Dodo, realizing that this is some sort of travelling machine -- possibly her ticket to adventure -- remains inside while the Doctor quickly relocates his Ship.

Meanwhile, in New York City, scientist Byron Carter informs investigative journalist Kathy Marchant that the rumours she's heard are true; an alien spacecraft landed somewhere near New York some days ago, at the same time that another craft crashed in London. Kathy's greatest desire is to prove the existence of extra-terrestrial life, as a form of rebellion against her estranged father, whose job as head of Project Blue Book is to hide the truth from the public. Shortly after contacting her, Carter is enlisted by General Marchant himself, to bring his skills as a biophysicist to bear on the ship and body recovered from London; however, Carter finds the job more than he can handle, as his faith in God is shaken by the existence of a non-human life form, in no way resembling Man made in God's image. The scientists at Rogers AFB begin to dissect the alien body but discover, too late, that it wasn't dead -- yet. Marchant has sent several of his men to New York City, undercover, to keep an eye out for any unusual happenings.

Five strangers with remarkable powers have arrived in New York City, where they walk the streets healing the sick and creating miracles. Theatrical agent Alexander Lullington-Smythe hears the rumours of their presence, and smelling a great business opportunity, tracks down the strangers and offers to orchestrate their introduction to the public. Meanwhile, the TARDIS materializes in New York City, having moved only in space and not Time, for some unknown reason. Steven roams the city alone, pondering his decision to leave the Doctor, while the Doctor and Dodo explore the city together. The Doctor hears rumours that the Gods of Myth have returned and follows the intrigued public to a run-down church where Smythe is introducing the Gods of the Latter-Day Pantheon. The Doctor confronts the Gods, fearing that they are hostile aliens here to conquer the world, but before he can do anything General Marchant arrives in response to a report from one of his undercover men. When the army storms the church, the Gods disappear, and the people with whom they were speaking are taken into custody.

While thinking about the Doctor's abandonment of Anne Chaplette, Steven is taken by surprised and stabbed by a mugger in Central Park. But as he lies dying, the God of Order (Norman) appears, heals his wound -- and, acting on Steven's instinctive desires, incinerates the mugger. Steven is appalled, and Norman realizes he has much to learn about the world he has come to save. Steven follows Norman back to the church, where the Gods' followers have gathered to await their return. Kathy Marchant had been sent to cover what she believed was an unrelated story, but upon seeing her father she has realized there may be a connection to Carter's earlier confession and is determined to prove the alien nature of the Gods. Norman speaks with Steven and Kathy and asks them how the Gods should go about saving their world, and while discussing the Gods' powers and how they should be used, Steven and Kathy are won over to his point of view and agree to help him spread the word of the Gods. The more people who know about them, the more people they can help.

Upon arriving at Rogers AFB, the Doctor's alien nature is discovered, but before Marchant can do anything Joseph unexpectedly arrives and begins to kill the people who killed his crewmate. Dodo stops him, telling him that it's wrong to kill, and he accepts her word as a friend and goes to New York to find the other Gods and see if they can tell him who he is. Dodo finally shares her story with the Doctor and General Marchant, and Marchant is forced to admit that he's out of his depth and asks the Doctor for help. He returns to the Gods' church with the Doctor, Dodo, Carter and Private Stanley Emerson. Before leaving the Doctor senses Carter's crisis of faith and convinces him to open his mind; the existence of an intelligent non-human life form should not contradict Carter's faith in a God who is surely capable of creating an infinity of wonders.

At the church, the Patriarch, the benevolent father-figure at the head of the Pantheon, insists that he and his gods have come to save the people of Earth, but the Doctor believes that the gods are trying to conquer Earth by convincing the people life would be better under their rule. Marchant is swayed by the argument that the Gods could intervene on wars on his behalf, but becomes convinced that this is the result of alien mind control and attempts to shoot the Patriarch. The Patriarch, infuriated, tries to kill him, but instead ends up killing Private Emerson when Emerson intervenes. Much to the Gods' shock and grief, they are unable to return the dead to life. But even this unfortunate incident does not convince them to leave the Earth. Instead, they march to Central Park with their believers and create a Gateway to Heaven at the end of a Rainbow Bridge. Carter decides that he wants to see the true face of God, and the Gods allow him to pass through the Gateway into Heaven -- though those who enter can never return.

As the Gods continue to dispense miracles and grant wishes free of charge, Smythe insists that they start charging and that he be given his due. But the Gods now have other followers who believe Smythe should be taught a lesson, and they temporarily transform him into a leech before dismissing him. Furious and humiliated, he vows revenge and agrees to help the Doctor and Marchant to discredit the Gods. Steven, meanwhile, begins to become disillusioned when the Gods allow more people to pass through the Gateway, which is tantamount to committing suicide. The Doctor, studying people's reactions to the Gods, finally realizes that the aliens are blank slates in their natural form; their forms, powers, and personalities on Earth have been shaped by those who observe them. The people of Earth have cried out for higher powers to save them from themselves, and thus that is what the aliens have become. But as their influence grows they will inevitably come into contact with contradicting faiths and beliefs -- and what will they do when they find themselves faced with problems they cannot solve?

Joseph seeks out Dodo and takes her through the Gateway, intending to make her happy forever. Steven is unable to stop him, and finally accepts that he's serving the wrong side and throws his lot in with the Doctor. He and Kathy begin gathering evidence that the Gods are not all-powerful and spread those stories amongst their followers. The Gods, just as the Doctor had predicted, are becoming confused and distressed by the conflicting demands placed on them; they are asked to kill a rapist in a prison cell while being told that killing is wrong, they are approached by members of the Ku Klux Klan who wish a definitive statement on the inferiority of the Negro... When two neighbours come to the Patriarch to settle a petty border dispute he loses his temper and smites one with a fireball, conforming to the image of a vengeful Old Testament God. The Doctor, hoping to prevent any further deaths, confronts the Patriarch and provokes him into attempting to strike the Doctor down, but the Doctor's belief in himself outweighs the people's shaken belief in the Patriarch and he is only slightly singed. The Gods' power is waning, but as decent people turn away from them, who will be left to shape what they are becoming?

Dodo finds herself a princess in a fairy-tale Heaven, just as she'd always dreamed -- at least until class-conscious knights storm the castle and hack her family to bits. Carter rescues her, and as they flee across a hellish landscape he explains the true nature of the aliens; the Gateway has sent them to the aliens' home world, and as more and more people pass through in the belief that they are entering Heaven, their conflicting views on the nature of the afterlife are tearing this world apart. Joseph, seeing Dodo's distress, tries to make her happy by proposing marriage, but just as the Patriarch is about to seal their union with his blessing, Carter points out that Joseph is fixating on Dodo because she has been the greatest influence on his personality. Joseph realizes that Carter is right, and admits that he doesn't want to marry Dodo if it isn't something she wishes for herself. The Patriarch, furious with Joseph for responding with the ambiguity and uncertainty of their human worshippers, turns him into an ordinary human.

The Patriarch returns to Earth and announces that, to ensure his followers' worship and respect, he and his Gods will travel to Vietnam and eradicate the Communist warmongers from the face of the Earth. Marchant is tempted to let him do so but must accept the Doctor's argument that the Gods would then never be stopped. Steven and Marchant's soldiers spread out amongst the few remaining worshippers as the air force springs into action, and as an aerial battle breaks out between the fighters and the Gods, Steven and the soldiers spread doubt and uncertainty that the gods can survive the battle. Finally, when the gods' power is at their weakest, the military drops a bomb on the Sheep Meadow. Even the gods' followers are certain that they cannot survive, and thus, even though the bomb is an unarmed decoy, they don't.

Joseph still retains his natural powers after all; the Patriarch could only make him appear to be human. He keeps the Gateway open so the humans who have passed through can be returned to Earth, and although he and Dodo must part, he hopes that he can hold onto his individuality and protect his own people from their nature. Once the Gateway is closed, Marchant begins to cover up the incident by blaming hoaxsters and using Smythe as a scapegoat, much to his daughter's disgust. The Doctor prepares to depart, and Steven accompanies him, although he still hasn't forgiven the Doctor for leaving Anne Chaplette to die. Dodo accompanies him as well; at last, her dreams of travel will come true.