The Doctor, sensing that there’s more to his new companion Grant Markham’s robophobia than even Grant realises, decides to take Grant back to his home colony of Agora to investigate -- only to find that it is a breeding ground for the Cybermen. Finding the defenceless colony an easy conquest, the Cybermen placed human Overseers in charge, and have returned every three years to select the 500 healthiest of its population for conversion into Cybermen. The Overseers, currently led by the sadistic Madrox, rule with impunity; anyone who speaks out against them is sent to the euphemistically named Population Control. Fifteen years ago, an attempted rebellion failed when the cowardly Ben Taggart chose to surrender rather than to sacrifice himself triggering a bomb in Population Control. Ever since, Taggart has served as an Overseer, but has been torn apart with guilt and self-loathing. The rebel Ted Henneker and the scientist Maxine Carter are planning another strike, and although Taggart doesn’t know the exact details, he has been helping them by passing on information from Population Control -- although unwilling to do anything to risk his own life or safety.

The Cybermen have supplied the Overseers with equipment with which to detect the arrival of the Doctor’s TARDIS should he appear, and the Doctor is captured and locked up almost as soon as he steps out of his ship. Grant, lost and alone, manages to contact the rebels and assists Maxine and Henneker in their Project. The Doctor is sealed in an escape-proof cell, where Madrox tries to torture information out of him, demanding to know who and where his companions are. The Doctor realises that the bullying Madrox is in fact terrified of the Cybermen, as he knows just what will happen to him if he fails to carry out their orders. Taggart is unwilling to risk his life to rescue the Doctor, who thus spends three weeks imprisoned in Population Control. Over those weeks, the Project nears completion thanks largely to Grant’s technological know-how, gathered from his years on New Earth; however, he still doesn’t know how he ended up there, as his memories of escaping Agora are largely a blur.

Two more time-travellers arrive on Agora from a University of the future, on a mission to interview the survivors of the Cyberman occupation. ArcHivist Hegelia has made the study of the Cybermen her life’s work, and Graduand Jolarr is beginning to realise that she has become dangerously obsessed by them -- but even he is horrified when she reveals that she altered their destination co-ordinates and has set them down in the final year of the Cyber-occupation rather than after their defeat. Grant emerges from the rebels’ hidden bunker to investigate reports of the aliens’ arrival, but he, Hegelia and Jolarr are all captured by the Overseers. Madrox concludes that Hegelia and Jolarr are the Doctor’s companions, and locks Hegelia up with the Doctor without listening to her attempt to explain her true agenda. Hegelia is surprised and disappointed to meet the legendary Doctor in person. Grant, meanwhile, gives Madrox a false name and claims that he’s returned to the city after tiring of the harsh life of the farms; the Cybermen have altered the climate and made it nearly impossible to grow crops. Madrox decides that the young man is good breeding stock and a good potential convert, and releases him with a warning.

Taggart recognises Grant for who he really is, and convinces Grant to take him to the rebels’ bunker. Grant does so, realising too late that Taggart hadn’t known its location beforehand. Upon arriving, Taggart is shocked to learn that, using Cyber-conversion material looted from Population Control during the failed rebellion, Maxine and Grant have transformed volunteers into “Bronze Knights”, cybernetic warriors who will defend Agora against the Cybermen. Henneker also plans to undergo conversion into a Bronze Knight, but before doing so he orders Taggart to release Jolarr. Taggart reluctantly risks his life to do so, but like Hegelia, Jolarr refuses to interfere with history by releasing the Doctor. Meanwhile, Madrox finally questions Hegelia and learns that one of the Sixth Doctor’s companions is named Grant Markham. Madrox recognises the name, realises who he was holding prisoner earlier and realises that Taggart, of all people, must have known the boy’s real identity. Furious, he has Hegelia locked up with the Doctor again, planning to lie and tell the Cybermen that Hegelia is the Doctor’s companion.

The Cybermen arrive to collect their 500 converts, and to cover his own failures Madrox reports that Taggart has betrayed them. Taggart is tortured until he reveals the location of the rebel bunker, and is then sent to the conversion chambers in Jolarr’s place. The Doctor apparently escapes at the last moment, but realises that his escape was too easy and that the Cybermen have allowed him to reach the TARDIS. The Doctor thus refuses to open the door and is recaptured. Hegelia contacts the Cyber Leader and claims that she wishes to undergo conversion of her own free will in order to complete her understanding of the Cybermen. She is shocked when the Leader rejects her offer; believing her to be a companion of the Doctor, he intends to torture her until the Doctor hands over the TARDIS, a greater prize. Hegelia and the Doctor are chained up in the conversion chamber, where Hegelia, realising that the Cybermen will not accept her offer, reluctantly helps the Doctor to escape. He overpowers the Cybermen operating the conversion machinery, but finds that he has acted too late; the first stage of conversion is already complete, and the colonists can no longer be separated from the conversion equipment. The Doctor must either kill them or face the prospect of five hundred Cybermen being unleashed upon the colony. He activates the cryogenic storage process prematurely in order to postpone the decision.

Jolarr seeks shelter at the bunker, but when he refuses to change history by giving advance knowledge to the rebels, the now-emotionless Bronze Knights threaten to “extract” the knowledge from him. As Jolarr flees in terror, Grant and Maxine begin to wonder whether the Bronze Knights will end up being no better than the Cybermen. The Cybermen searching for the bunker spot Jolarr emerging from it and attack, but they aren’t expecting the Bronze Knights to be there. In the ensuing battle, the Bronze Knights suffer heavy casualties, but destroy the attacking Cybermen and then take the fight to Population Control. When Madrox realises that the Knights are winning, he seeks to curry favour by shooting at the Cybermen with his Overseer-issue microwave gun -- and is surprised when it actually kills a Cyberman. The Knights are about to kill him anyway for his collaboration, when the Doctor arrives with bad news; before he was destroyed the Cyber Leader sent out a distress call and summoned reinforcements. Meanwhile, Jolarr discovers that the ArcHive timeship has vanished.

As the Bronze Knights prepare for the arrival of more Cybermen, Grant speaks to the dying Taggart, who admits that he is Grant’s father; due to Agora’s nature as a “breeding colony,” children take their mothers’ surnames. Taggart explains that soon after the failed rebellion, a spaceship appeared from nowhere in the fields, and a few sympathetic Overseers managed to smuggle some children on board and programme the autopilot to take them to New Earth. As Taggart dies, Grant realises that his robophobia comes from repressed memories of seeing the Cybermen kill his mother during the rebellion.

The Cybermen arrive in a stolen Selachian battle cruiser, and the Doctor, recognising the ship and its weaponry, manages to evacuate the complex just as the Cybermen begin firing its plasma weapon. Selected areas of Population Control are destroyed, and the Cybermen then destroy an entire village and its population just to make their threat clear. Unless the Agorans surrender within an hour, another village will be destroyed. The Bronze Knights refuse to surrender, and order the citizens to begin volunteering for conversion into more Knights to swell their numbers. One man stands up to them, refusing to accept their orders, and Henneker kills him. He then orders the furious Doctor to use his TARDIS to transport them to the Selachian ship, but the Doctor refuses to do so, feeling that the Knights have already progressed too far along the same path as the Cybermen. Henneker concludes that since the Doctor is not helping them he is their enemy, and orders that he be locked up until he changes his mind.

Grant, unable to tolerate the horror any longer, asks Maxine to convert him into a Bronze Knight, but she talks him out of it; horrified by the death of the colonist, she has begun to question her actions, and to wonder how the conversion process has affected Henneker. If he no longer thinks or acts like he used to, is he still the same person? Grant releases the Doctor, who orders him to distract the Cybermen by using his programming skills to make it seem as though the conversion machinery has been reactivated, while the Doctor takes his TARDIS to the Selachian ship alone. Jolarr, horrified by the destruction of the innocent villagers, finally accepts that he has become a part of events and agrees to help Grant.

What neither of them yet realise is that Hegelia has released Madrox, entered the Cyber-conversion chambers and ordered Madrox to operate the machinery; if the Cybermen will not convert her, she will do it herself. Hegelia begins to record her impressions as the conversion machinery sets to work, tearing her flesh apart and replacing it with bionic implants; however, as her brain is augmented with a computer unit, she finds her individuality dispersing into the Cyber-will, until all that had made Hegelia unique is gone forever. The new Cyberman accesses Hegelia’s memories and recalls that the Cybermen have been defeated, and when it emerges from the conversion machinery, it kills Madrox and activates the remaining conversion units. When Grant and Jolarr arrive, they find five hundred new Cybermen emerging from the conversion chambers. They escape back into the colony and warn the Bronze Knights of the danger, and a battle breaks out between the Knights and the Cybermen. Grant, forced to conquer his robophobia and think clearly, theorises that since the Cybermen were to be cryogenically frozen for their departure from Agora, low temperatures may cause them to shut down automatically. He and Jolarr flood Population Control with freezing gas, and as Grant had predicted, the attacking Cybermen shut down.

The Doctor materialises on the Selachian warcraft and attempts to sabotage it, but he is captured and taken to the Cyber Leader. The Leader orders him to surrender his TARDIS, and when the Doctor refuses, the Cybermen target another settlement and fire the plasma weapon, believing that the Doctor’s emotional weaknesses will eventually drive him to surrender. They learn too late that the Doctor had already completed his act of sabotage; the radiation blast from the plasma weapon, instead of being focussed upon the planet, seeps back into the ship. As the Doctor had guessed when he learned that a Cyberman had been killed with a microwave gun, these are Cyber-nomads, still reeling from the war with Voga and short on resources; thus, they have been using more organic material than normal, and as a result, they are susceptible to strong doses of radiation. The Cybermen on the ship are all killed by the radiation blast, but the Doctor, though suffering from radiation poisoning himself, manages to get back to the TARDIS and to the drugs which will save his life.