The TARDIS materialises in the middle of a party on a privately owned planetoid. The Eknuri are an offshoot of humanity who have pushed their minds and bodies to the limits, achieving physical and mental perfection. Peri is swept away by the beautiful Athon, and when he offers to take her on a tour of his planetoid she accepts without hesitation. However, it doesn't take her long to realise that the complacent Athon is interested only in himself and his own pleasure, and that the Eknuri's attitude towards sex is far more casual than her own. When Athon tries to go further and faster than she's willing, she demands to be taken back to the party immediately; but as they turn about, their skyboat is attacked by an alien ship which appears as if from nowhere and guns them down. The terrified Athon tries to flee, but fox-like humanoid aliens descend from the ship on portable helicopter-packs and seize him, leaving the damaged skyboat to return to the party on autopilot. Peri refuses to show fear to the aliens, who seem to respect this even as they shoot her where she stands...

Back at the party, the Doctor meets Aline Vehlmann, a former xenologist who is trying to return to work after a disturbing encounter with an alien force so ancient and powerful that exposure to it drove her mad. On one level she's delighted to meet one of the legendary Time Lords; on another, she fears that exposure to something so alien may cause her to suffer a relapse. The Encounter has also left her psychically receptive, and when Athon's empty skyboat crashes on the beach, she senses that something terrible is about to happen. The Eknuri have detected the arrival of the alien ship, but their reliance on the superior defenses and reputation of their homeworld has left them certain that nobody would dare attack them. The Doctor takes Aline to the beach to investigate, telling the complacent Eknuri to be prepared for anything; but they ignore his warnings, and when the fox-like aliens attack, they are caught entirely off guard.

Aline recognises the aliens as Valethske, vicious and savage killers reputed to feed on human flesh. She and the Doctor hide in the nearby caves, and although Hunt Marshal Veek sees their footprints on the beach, Commander Kikker recalls his hunters to the ship before she can follow them. Veek is more than just disappointed; it's been too long since she experienced the thrill of a good hunt, and she's beginning to consider abandoning the Great Mission altogether. The Valethske return to their mothership with their prey, and as soon as the coast is clear the Doctor and Aline rush back to the TARDIS. They are too late; the Eknuri have all been taken prisoner, apart from those whom the ravenous Valethske ate on the spot, and the Valethske ship has engaged a primitive FTL drive which prevents the TARDIS from materialising on board. The Doctor won't be able to rescue Peri until the ship reaches its destination in a century's time. Aline, realising that she must face her xenophobia at some point, agrees to travel into the future with the Doctor to rescue their friends.

The Valethske have cryogenically frozen themselves and their prey for the journey, and the ship has been depressurised. The Doctor has only seven oxygen masks, and thus he and Aline can only rescue five people; they take Peri, Athon, the Eknuri Taiana and two human soldiers, but must abandon the other frozen victims to their fate. As they return to the TARDIS, the ship begins to repressurise, but only in certain areas -- and a bulkhead cuts off their retreat. Since the Valethske are awakening, the Doctor and his allies must steal a shuttle to escape, leaving the TARDIS behind. The Valethske's prey are revived first, so that the Valethske themselves will have a meal ready when they wake; however, Commander Kikker will only eat synthetic meat, for as a show of confidence he has vowed not to eat live meat until the Mission is over. As the terrified Eknuri are eaten alive in the pit, the technician Ruvis informs Kikker of the loss of a shuttle and the presence of a strange blue box on their ship. Kikker recognises the TARDIS from the raid, and realises that it must have travelled through time to catch up with them. It will be investigated thoroughly once this phase of the Mission is complete.

The stolen shuttle lands on a beautiful garden world, where the rows of plants seem cultivated rather than natural. The human soldiers, Captain John Melrose and Lieutenant Lornay Meharg, take command, intending to find some way to contact Korsair military command and wipe out the Valethske; realising that they are still traumatised by their experiences, the Doctor chooses not to tell them just how long they were frozen. In the meantime, their party sets off for the large Tree at the centre of the garden, hoping to contact the world's natives, despite Aline's warning that she can sense a presence on this world -- some force older and more powerful than humanity. As they draw nearer to the enormous Tree, they encounter mobile plants caring for the Garden, but Melrose dismisses them as unimportant. The Doctor, fearing that the blinkered Melrose could get them all killed, finally reveals that Melrose and Meharg have been frozen for five centuries. Unable to handle this revelation, Melrose storms off to learn the truth for himself, forcing the others back at gunpoint.

The Doctor tries to follow Melrose and talk sense into him, but loses him in the Garden. While he's gone, Peri gives in to her hunger and picks a fruit from one of the trees, finally drawing the Gardeners' attention. Meharg incinerates the Gardeners as they approach, to the Doctor's disgust. As they continue on towards the Tree, they realise that this is where the Gardeners are taking the harvested fruit; presumably the Garden's inhabitants live in the Tree. Evening has fallen, and the Doctor decides to wait for morning to investigate -- but the presence which Aline sensed earlier is calling to her, and she gives in and follows the call to the Tree. The Doctor follows her, realising that the presence is in fact responding to the echo of the alien left in Aline's mind by her previous Encounter. Upon entering the Tree she is overwhelmed by the force of the call, and before the Doctor can stop her she throws herself into the depths of the Tree along with the Gardeners' harvest.

Athon tries to apologise to Peri, but she realises that he just doesn't want her to think badly of him; he's still just as selfish as ever. When she rejects him, he turns his attention to Meharg, who is more open to his approach. However, Peri and Taiana then see a spaceship coming in to land -- the Valethske have finally tracked down their shuttle. The Valethske interrupt Athon and Meharg as they make love, and Veek's mate Flayoun shoots Meharg dead when she tries to flee. Peri and Taiana head for the Tree to warn the Doctor, but the Valethske catch up to them all. The Doctor tries to bargain for their lives by claiming to have information about the blue box on the Valethske ship, but they ignore him and shoot all three of their captives with tranquiliser darts. Out in the Garden, Melrose sees the Valethske arrive, and, realising that they will try to reclaim their stolen shuttle, he ambushes their party, killing two of them and wounding a third. But the Garden has been changing in response to Meharg's earlier attack -- and as Melrose prepares to torture the third Valethske to death to avenge his fallen comrades, killer Gardeners with poisonous thorns emerge from the shadows and tear him apart.

The Valethske begin drilling through the Garden to the tunnels they have detected underground. Ruvis has Peri, Athon and Taiana stripped naked and dropped into the pit with the remains of the other Eknuri; should this not be the world they're looking for, Ruvis intends to breed prey aboard the mothership in order to save time. Veek finds the concept of farming prey offensive, further proof that the Mission is causing her people to forget what it means to be a Valethske. Meanwhile, Kikker interrogates the Doctor, who confirms that the blue box is indeed a time machine -- one which only he can operate. And he will only co-operate if his friends are left alive. Kikker reluctantly orders his hunters to put their prey to work clearing rubble from the excavators until the Doctor's claims are confirmed.

One look inside the TARDIS confirms that it is the product of an advanced civilisation, and Kikker decides to have the Doctor cryogenically frozen until the Mission is complete. The Doctor questions Kikker about the Mission, and Kikker finds that he enjoys explaining it to a non-Valethske. Long ago, the Valethske worshipped the Khorlthochloi, an ancient species which acted as shepherds to the younger races; when the Valethske became too widespread and vicious, the Khorlthochloi destroyed their warfleet and struck them down with a plague, forcing them to rebuild their civilisation from scratch. The Valethske are culturally incapable of regarding this as just punishment for their savagery, and although the Khorlthochloi apparently vanished from the Universe long ago, Kikker's ship has been following clues and legends for centuries, in the hope of finding them and exacting revenge. Kikker believes that the Garden is the world which the Khorlthochloi built for their retirement -- and once the Valethske find their gods, they will destroy them.

As the Doctor's friends work at the excavator, Flayoun and the other Valethske give in to their savage instincts and tear into Taiana, eating her alive. Peri and Athon take advantage of the distraction to flee down the drill shaft into the tunnels, but they are pursued -- and Athon, refusing to let the Valethske take him alive, commits suicide by detonating a mining charge, blowing himself up and killing the pursuing Valethske. To Veek, this is the last straw, and she suggests to Flayoun that they take advantage of the incident to abandon the Mission and return home to Valeth Skretta. She has underestimated his committment to the Mission, however, and he tries to kill her for her heresy. She defeats him, but allows him to live in shame. Meanwhile, Peri makes her way through the tunnels to a cavern where she finds the dying Aline. Aline has encountered a stream of plasma, infused with energy too powerful for her frail human body to handle, and although she has learned the truth about this world, her body's cellular structure is falling apart. Peri flees when a herd of beetles the size of small cows scurries into the cavern, unaware that the beetles are the true inhabitants of the tunnels -- the entire Garden has been set up just to feed them.

The Doctor tricks his guards, steals a gun, and threatens to shoot himself and thus deprive the Valethske of time travel unless they take him to his friends. They take him to the excavator, but by this time time an army of poison Gardeners has attacked the Valethske ship, and Kikker is otherwise occupied. When Veek and Flayoun arrive, Flayoun accuses Veek of heresy, but she overpowers the Doctor and takes back his gun; since Flayoun can't deny that he disobeyed orders and ate one of his prisoners, Kikker accepts Veek's word over his. He thus orders Veek to take the Doctor to the cryogenic facility -- but once they're out of earshot, Veek demands that the Doctor take her back to her homeworld instead. The threat of death does not faze the Doctor, and Veek is thus forced to make a deal with him; if he agrees to take her home, she will help him to find and rescue Peri. Ruvis is in the laboratory when they arrive, and despite the Doctor's objections, Veek kills him in order to get to the TARDIS. The Doctor takes her into the tunnels to search for Peri, but instead they find the cow-beetles and the dying Aline, who tells them that the Valethske are too late. The gods are already dead...

Peri finds her way out of the tunnels, only to run into a group of Valethske fighting their way past the killer Gardeners. Fortunately, Flayoun is one of them, and he knows that he must keep her alive to restore his honour. He thus takes her back to the Valethske ship, where she is chained up on the bridge while Kikker recalls his hunters, intending to destroy the planet from orbit. As he does so, he discovers that the Doctor, Veek, and the TARDIS are all missing, and realises that Flayoun was telling the truth. Kikker thus promotes Flayoun to Hunt Marshal, and takes the ship into orbit, and to Peri's horror, the Valethske launch a barrage of Scourblaze missiles and incinerate the surface of the planet, destroying the Garden forever. Although the Doctor has apparently gone, Peri is allowed to live, but only because Kikker is convinced that this is indeed the home of the gods; when the Mission is finally over, Kikker will once again be able to feast on live flesh, and Peri will be his first meal.

Before the Doctor, Veek and Aline can return to the TARDIS, Kikker and his hunters arrive and capture them -- but just as Kikker appears triumphant, Aline tells him what she's already told the others. The Khorlthochloi abandoned their physical bodies thousands of years ago, passing into a dimension of pure mine, and establishing the Garden to tend to their bodies. In the event, they encountered a threat on their new plane of existence, but their bodies' autonomic nervous systems were so highly evolved that they rejected the Khorlthochloi's minds when they tried to return. Their last action before their astral enemy destroyed them all was to embed a warning in the plasma strand at the centre of the Garden; the echo of Aline's earlier Encounter confused it, and it reached out to her, believing her to be a higher evolutionary. Over the millennia, the Khorlthochloi's physical bodies have devolved into mindless insects once again; now that the Valethske have incinerated the Garden, they will soon die out. But the minds of the Gods died long ago, and Kikker has missed his chance for revenge.

The Doctor takes Kikker to the plasma strand to confirm his story. While they're gone, Flayoun challenges Veek to a duel, and while they fight, Peri and Aline slip away. Veek defeats and kills Flayoun, and tries to turn the other Valethske to her side; but before they can decide, Kikker returns with the Doctor, having decided to force the Doctor to take him back in Time so he can destroy the gods himself while they still live. But Peri and Aline have reached the plasma strand, and before Peri realises what she's doing, Aline deliberately steps into it and releases the energy embedded within it upon the Valethske. In the confusion, Veek kills Kikker and gets into the TARDIS with the Doctor, and as soon as the energy storm dies down the Doctor picks up Peri; however, he is too late to save Aline, as this second exposure to the plasma strand has finished her off.

Peri is appalled to learn that the Doctor has made a bargain with Veek, and threatens to leave his company if he allows Veek to travel on the TARDIS with them. The Doctor comes up with a compromise, offering to improve the Valethske ship's FTL drive so Veek and her surviving people can return home more quickly. Since the Mission is now over, Veek accepts his offer. She has learned a grudging respect for the Doctor, and no longer regards him as mere prey; but she is still a Valethske, and she will continue to hunt humans for sport and food. As the Valethske ship takes off, Peri admits that she spoke in anger, and that she still wants to travel with the Doctor; but she can't forget the death and destruction which the Valethske have caused, and she is starting to realise just how alien the Doctor's morality can seem... and how dangerous travelling with him can be.