The Fourth Doctor, traveling alone in the TARDIS, arrives on a mysterious jungle planet which he cannot resist exploring. He soon encounters Leela, a savage from the local tribe, who denounces him as the Evil One of fable amongst her people. She has been exiled from her tribe, the Sevateem, for profaning their god, the mysterious Xoanon, which speaks to them through the tribe’s shaman, Neeva. Her father, tribal elder Sole, tried to intervene to protect her but died when taking the Test of the Horda on her behalf. Now Leela is an outcast beyond the invisible barrier around her tribal home. Neeva, meanwhile, has sent two men to murder her, an action witnessed by Leela's friend Tomas, who kills one of the men as Leela dispatches the other. In the jungle beyond that she encounters the Doctor, who soon wins her over by defending her from invisible monsters that rampage about, attracted by vibration of any kind. Exploring further, the Doctor finds a sophisticated sonic disruptor which creates the forcefield that keeps the creatures from attacking the village itself. Leela regales him with more folklore of her people: the god Xoanon is kept prisoner by the Evil One and his followers, the Tesh, beyond a strange black wall.
The Sevateem have meanwhile decided to launch an attack on the domain of the Tesh to free their god. They are led by the combative Andor, who is determined to free his god, and also believes that an attack will unite the people. Andor suspects Neeva of being a false prophet, and Tomas tells him of Neeva's assassination attempt against Leela. Still, Andor believes the attack will succeed and is prepared to go ahead.
Two warriors are scouring the jungle when they find the Doctor, and they too call him the Evil One, making a protective hand gesture which the Doctor interprets as the sequence for checking the seals on a Starfall Seven spacesuit. The warriors seize the Doctor, but not Leela, and take him to the village council, where his face is shown to all the tribe. Andor is convinced the prisoner is the Evil One, and has him confined. However, Leela manages to free him by using poisonous Janis thorns, which paralyze, then kill the victim. The Doctor is horrified by this and instructs her "No more Janis thorns, Ever".
The pair flee the village and head to a clearing beyond, in which the Doctor is greeted with a stunning sight: carved into a mountain nearby is an impression of his own face. The Doctor cannot recall clearly why his face is depicted so, and persuades Leela to return to the village to find out more, despite the death sentence upon them. They return to Neeva’s holy tent and the Doctor inspects the ancient tribal relics, recognising them as artifacts from an Earth survey expedition. He also finds a transceiver used by Neeva to hear the commands of Xoanon. It speaks with the Doctor’s own voice, conveying exhilaration on hearing the Doctor that "At least we are here. At last I shall be free of us."
They then head off to inspect the dark Wall that stands at the entrance to the realm of the Evil One. The Doctor deduces it is a primitive time barrier, and is convinced the Sevateem warriors will be massacred if they attack the fortress of their enemy, the Tesh. From a distance they see the massacre unfold, as laser beams cut down warriors armed only with crossbows and other basic tribal weapons. Half the tribe is lost in the assault and one of the elders, the devious Calib, is first back at the camp where he finds the Doctor and Leela. He is evidently intent on using the Doctor to break Neeva’s hold on the tribe by exposing the faith in Xoanon as misplaced mythology. Leela’s friend Tomas also arrives, and is appalled to find Calib has stabbed Leela with a Janis thorn to prevent her exposing his schemes. The Doctor gets Tomas to help him move Leela to Neeva’s tent, where he uses a bio-analyzer to synthesise an antidote to the poison.
When the surviving warriors return, the Doctor, Leela and Tomas are invited to address the tribal elders in defence of their lives. Leela makes matters worse when she accuses Xoanon of causing the trap at the Wall. Calib intervenes to suggest the Doctor is not the Evil One, and this can be proven by getting him to take the fabled Test of the Horda. In the centre of the village is a pit full of Horda, two-foot-long worms which hunt in packs and react to the movements of their prey. They are reputed to strip flesh from a man in an instant. The Sevateem evolved the Test of the Horda as a measure of justice and bravery. It involves suspension on a rope above the pit, and accused characters are gradually lowered into the pit by means of a rope. The Doctor is given a crossbow which has to be fired at the exact moment to sever the rope without causing him to fall into the pit – which is, of course, the fate of the guilty. The Doctor succeeds, and is therefore presumed to be a non-malign influence and freed. He proceeds to examine some relics of the tribe and repairs a disruptor gun. He also tells some of the tribe that the Sevateem are the descendants of a “survey team” which left a Starfall Seven Earth colony ship. The Doctor and Leela then go to examine the face in the mountain, and they climb into the face by scaling the Doctor’s teeth.
Neeva returns to his tent, where the voice of Xoanon tells him that the tribe will be destroyed, and the mysterious being then causes the sonic disruptor to shut down, leaving the village open to attack from the invisible beings. These descend on the village, killing indiscriminately, including crushing Andor to death. Tomas uses the disruptor gun built by the Doctor to expose the true appearance of the invisible beings: they are ferocious, angry depictions of the Doctor’s own face as shown in the picture.
Leela and the Doctor notice a figure in a space suit in the “mouth” entrance and follow it through a projection of a wall. Beyond this barrier is a rocket, which the Doctor recalls as belonging to the Mordee Expedition, his memory of events earlier in his regeneration now returning. Xoanon has detected the Doctor nearby, and when he reaches the ship the god-creature is both ecstatic that "We are here” while also manically pledging that "We must destroy us."
The Doctor and Leela now meet three representatives of the Tesh, who serve and worship Xoanon. They are human too, but technologically advanced and possessing telepathic abilities. The Doctor deduces both Sevateem and Tesh are descendants of the same crew from the Mordee Expedition, with the Tesh (or technicians) involved in the same deadly eugenics exercise as the Sevateem (or survey team).
The invisible creatures that attacked the Sevateem are also part of the same deranged scheme: Xoanon is a highly sophisticated computer, designed to think independently. The Doctor had once repaired Xoanon but forgot to wipe his personality print from the data core, leaving the computer with a split personality. The Doctor and Leela are soon imprisoned but evade their captors and find the remote communications device used to communicate with Neeva. The Doctor, speaking as Xoanon, instructs Neeva to tell Calib, who is now tribal leader, to lead the Sevateem survivors through the mouth of the carved face in the mountain. Calib accepts this instruction and leads them into the safety of the mouth, where the invisible beings can no longer threaten the tribe.
With Leela keeping guard and holding the Tesh at bay with a disruptor gun, the Doctor ventures into the computer room of the ship to confront Xoanon. He blames himself for creating the maddened split personality of the computer and now attempts to persuade it to shut down. When Xoanon refuses it channels a vicious mental assault at the Doctor, causing him to collapse. As the Doctor writhes on the floor, Xoanon booms: "Who am I?"
Leela rescues the Doctor from the mental assault, and as he recovers he warns her of Xoanon’s power. Moments later they realise the computer has electrified the walls to try and kill them, and the Tesh become more purposeful in tracking them down within the spaceship. The Tesh also come under attack from Calib, Tomas and the survivors of the Sevateem, who now reach the spaceship too. This diverts the Tesh while the Doctor and Leela return to the computer room, where Xoanon briefly takes control of Leela’s mind. Most of the Sevateem come under the telepathic control of the computer too.
The Tesh and Sevateem soon converge on the computer room too and interrupt the Doctor as he tries to repair Xoanon, realising the computer has now triggered the countdown to an atomic explosion. Elsewhere in the ship Neeva is alone but crazed, his faith in Xoanon shattered. The shaman uses the disruptor gun against one of the images of Xoanon/the Doctor projected through a wall. The ensuing blast kills Neeva but also interrupts Xoanon’s control of its subjects, allowing the Doctor to resume and complete his repairs. Xoanon’s circuits explode, knocking the Doctor out.
Two days later the Doctor wakes up to find himself aboard the spaceship in the care of Leela. She explains Xoanon has been quiet and he interprets this as success for his extraction experiment. They visit the computer room and find Xoanon’s identity and sanity restored. The computer confirms it was running a eugenics experiment and thanks the Doctor for his repair work. The Doctor then contacts the survivors of the Tesh and Sevateem and tells them Xoanon is now cured and able to support their new society. He then heads off to the TARDIS followed by Leela. She insists she join him on his travels, and when he refuses she jumps into the TARDIS with him and starts the dematerialisation process.