While fighting injustice on the planet Oolis, Benny befriends a Hith named Homeless Friendless, who is later shot and killed by the Oolian militia. As he dies, he warns Benny to avoid the Earth for the next few years, as something bad is going to happen there. After leaving Oolis, Benny tells the Doctor about Homeless’ warning, and the Doctor decides to investigate. He and Benny thus travel to 30th-century Earth, the centre of the expanding Earth Empire. The new rage is “body-beppling” -- using genetic modification to customise one’s personal appearance -- and the rich and powerful live in the floating Overcities, leaving the polluted surface of the planet to the poor and alien homeless. The TARDIS materialises in Spaceport Overcity Five, which was once called London, and the Doctor and Benny set off in the hope of finding another Hith who might be able to explain Homeless Forsaken’s last words.

Cynical and xenophobic Adjudicator Roslyn Forrester is given a new squire, fresh out of the Academy, but is irritated by his grating enthusiasm and the fact that he’s had himself body-beppled to resemble a huge teddy bear. Their first case together involves the murder of a homeless Hith named Waiting for Justice, but their prime suspect, a drugged-out homeless woman named Annie who was found holding a knife near the body, dies of a brain seizure while under the mind probe. Roz is prepared to close the case, but Chris points out that the image of the knife on the mind probe does not match the real knife taken as evidence, which implies that someone has tampered with Annie’s memories. Roz doesn’t particularly like her new partner -- she is still haunted by memories of her former partner Martle’s death, at the hands of the alien Falardi -- but she agrees that he has a point, and reports it to her superior Rashid. Rashid orders them to close the case, but Chris notices that she has been transmitting their entire conversation to someone else. But why would the authorities put pressure on Rashid to stop investigating a homeless alien’s murder? It’s just one of many murders on Earth -- but the number of motiveless murders seems to be increasing, as perfectly ordinary people are suddenly turning on friends, family and total strangers for no reason whatsoever…

Another Hith, Powerless Friendless, uses a tiny creature named Krogh to open the electronic locks into the Overcity and busk for his supper in a city park. The Doctor and Benny find him there, and the Doctor notices scarring and prison tattoos on the Hith’s flesh. He tries to question Powerless Friendless, but only stirs up bad memories which the Hith had been trying to forget. Powerless Friendless flees back down to the Undercity, but is spotted and pursued by a killer robot -- the same robot who turned Annie over to Chris and Roz… Powerless Friendless escapes, but now knows that someone wants him dead. The time has come for him to return to memory-sculptor Doc Dantalion, and reclaim the memories which he had tried to erase.

The Doctor’s only lead is Powerless Friendless’ prisoner ID tattoo, and he thus decides to visit the Imperial Landsknechte headquarters on the planet Purgatory to look up the ID number. However, the TARDIS is no longer where it materialised -- and the Doctor fears that it’s been taken by someone who recognised it for what it is. He and Benny buy tickets and go to Purgatory by spacecraft, and on the way, Benny has an odd conversation with a remarkably erudite purser robot. Meanwhile, their enemy radios ahead to Provost-Major Beltempest on Puragatory and orders him to kill them upon arrival. He has already set another trap for them on Earth; when Chris and Roz examine the record of Annie’s mind probe, against orders, they find Annie was apparently drugged and sent to kill Waiting for Justice -- by the Doctor and Benny.

Purgatory is a patchwork planet, where the Landsknechte are tested to destruction in discrete hexagaonal environments terraformed to resemble all of the alien worlds in the Empire where they might conceivably have to fight. Upon arriving, the Doctor uses his regenerative powers to fool the genetic scans at the spaceport, and he and Benny access the Landsknechte database. Powerless Friendless’ ID number is still classified, as is a second ID number which the Doctor deduces belonged to Homeless Forsaken. Before he can investigate further, Beltempest captures them, informs them that they have been identified as enemies of the state, and sentences them to death by training exercise. By the time Roz and Chris arrive to request their suspects’ extradition, the Doctor and Benny have already been transported into the Ybarraculous Epsilon hexagon, to be hunted down and killed by Landsknechte.

The Doctor and Benny use the carnivorous flora and fauna of the jungles to hold off the pursuing Landsknechte, intending to get away from them, sabotage the force wall between this hexagon and the next, and steal the repair team’s shuttle. They are captured before they can do so, but the Doctor nearly succeeds in bluffing them into believing that this has been a test of their abilities. One of the Landsknechte, mad with impatience, suddenly turns on his fellows and guns them all down, but Roz, Chris and Beltempest arrive, and Chris shoots the madman before he can kill the Doctor and Benny. Before anyone realises what he’s doing, the Doctor cuts open the dead man’s head to reveal a line of fire in his brain, evidence that he had been exposed to a rare form of radiation. Icaron radiation has been known to cause psychosis in anyone who has undergone genetic manipulation, which means that anyone who has been body-beppled and exposed to an icaron source is now a potential psychotic killer. When the Doctor learns about the rising murder rate on Earth, he realises that this must be the disaster Homeless Forsaken warned Benny about. Beltempest, who seems to know something about the dangers of icaron radiation, agrees to let the Doctor investigate, but turns Benny over to Roz and Chris for questioning.

Back on Earth, Chris replays the mind probe records, but finds that the Doctor’s voice doesn’t match the one in the recording. Benny realises that their enemy must have failed to sample the Doctor’s voice -- and thus used the voice of one of his previous incarnations… Roz attempts to tell Beltempest of their discovery, but the enemy taps her call and decides that they must all be disposed of. He thus sends an anonymous tip which lures them to a deserted car park, where three military robots are waiting for them. The robots speak with the same voice as the robot purser which spoke to Benny on the spaceship to Purgatory, the one which sampled her voice for the mind probe records... Chris saves them all by hot-wiring a flitter and crashing it into the robots, but he barely ejects in time and is badly injured. Knowing that Rashid is in the pay of the enemy, and unsure how far the corruption extends, Roz has no choice but to take Chris to Doc Dantalion for treatment in the Undercity. As a side-effect, this will undo his body-bepple, restoring his human appearance. Dantalion agrees to treat Chris -- on condition that Roz allow him to restore a memory which he had been paid to erase from her mind some time ago. When Roz’s memories are restored, she recalls discovering that her partner and lover Martle was being bribed to carry out secret operations for the company INITEC. His contact, a robot in the shape of a man, ordered him to find and kill a certain Hith, one of two who posed a danger to the bot’s plans; the bot had already bribed the Oolian militia to dispose of the other one. Martle discovered Roz spying and attempted to kill her, and she killed him in self-defense; however, the bot then drugged her and arranged for its contacts within the Adjudicators to erase her memory of the incident.

Powerless Friendless has already visited Doc Dantalion, and restored his own memories; but in his case, he’s the one who requested that they be erased. Towards the end of the war between the Hith and the Earth Empire, Powerless Friendless was the navigator on an experimental new ship whose captain sold them out to the enemy. Powerless Friendless was taken to the INITEC building and tortured for information, but was rescued by his captain, who had realised too late that the humans had no intention of honouring their deal with him. By that point, Hithis had been conquered and terraformed, and all Hith everywhere had renamed themselves to reflect their new status as galactic nomads; the traitorous captain renamed himself Homeless Forsaken and retreated to Oolis to live in shame. Powerless Friendless, unable to bear the knowledge that his trusted captain’s treachery led to the destruction of their homeworld, paid Doc Dantalion to erase his memories. Now that they have been restored, Powerless Friendless goes to the INITEC building to seek revenge. Meanwhile, the number of random murders continues to increase, and sporadic riots begin to break out in the Overcities. A state of emergency is declared; anyone who commits murder may now be legally reclassified as a hostile alien, and vivisected to determine the cause of their insanity.

The Doctor and Beltempest determine that most of the people convicted of murder in the past few months had passed through Spaceport Five Overcity at some point. They still need to find the source of the icaron radiation, however, and Beltempest thus reluctantly takes the Doctor to meet the foremost human authority on icarons, Professor Zebulon Pryce. Pryce was driven mad while researching icaron-based weaponry on Purgatory, and killed several of Beltempest’s friends before he was caught and arrested. He was sentenced to life imprisonment on Dis, a prison within the photosphere of a star; but since he is their only lead, Beltempest arranges for him to be released into their custody. As they leave Dis, Pryce twists a drinking cup into a weapon and threatens to put out the Doctor’s eyes unless he can prove that murder is wrong. Much to Pryce’s amusement, the Doctor is unable to come up with a logical argument to prove his claim.

As Beltempest departs from Dis, a Hith cruiser unexpectedly attacks and captures their ship. The Hith take their prisoners to a secret hideout within the Hithis hexagon on Purgatory, kept hidden from the Landsknechte by the Hith working in the planet’s service industries. The Hith have been waiting for Pryce to be released for years, as only he can tell them where to find their missing experimental ship. The claim that Pryce was working on icaron-based weaponry was a cover story; he was in fact studying the icaron drive in the captured Hith ship. Since icarons are naturally at rest in hyperspace, any ship powered by an icaron drive could divert the energy normally needed for the hyperspace drive into more powerful weaponry. When Pryce went mad the ship was taken back to Earth -- and the Doctor and Beltempest realise that the ship must now be docked in hyperspace, somewhere relative to Spaceport Overcity Five, near a portal connecting it to realspace. Whenever the portal between the ship and Earth is opened by the research team, icaron radiation is released into the city, contaminating anyone within range…

The Earth Empire is currently considering a settlement which will allow the Hith to reclaim their homeworld, and as the revelation that a Hith ship is causing madness and riots on Earth would endanger those negotiations, the Hith have manufactured an organic control nexus with which to shut down the ship’s icaron drive. But they have underestimated Pryce, who breaks free and destroys the control nexus creature, leaving them with no way to power down the ship even if they find it. The Hith kill Pryce, but then receive a transmission from Powerless Friendless, who has remembered his former loyalties and informs them that the ship is being held at the INITEC building on Earth. The Doctor and Beltempest accompany the Hith back to Earth, where riots are spreading through the Overcities as more and more people fall victim to the madness. The Overcities themselves begin to fall from the skies as madmen sabotage their gravity drives…

Benny, Roz and Chris meet Powerless Friendless while breaking into INITEC, and together they locate the hyperspace portal and the Hith ship beyond. They are pursued into the ship by security robots, but the Hith fleet arrives in time to rescue them. While fighting alongside the others, Beltempest admits that he’s not really Beltempest, but an undercover agent; the real Beltempest was to be arrested for corruption, but their enemy had planted a post-hypnotic command in his mind and he shot himself when the arresting officers arrived. His “replacement” was given orders to play along with the enemy until he could find out who had bribed the real Beltempest to kill the Doctor and Benny. Powerless Friendless, meanwhile, finally realises that his “pet” Krogh, who has been opening locks for him for years, is in fact the original control nexus for the ship. Realising that his fellow Hith have no intention of shutting down such a powerful weapon, and blaming his own cowardice for letting the situation go on this long, he tells Benny to evacuate the ship while he programmes it to crash into the Undercity.

The Doctor senses the presence of the TARDIS within INITEC, and follows its call to an office occupied by the bot who watched Roz kill Martle -- a robot with the mind of the Doctor’s old enemy Tobias Vaughn. Vaughn had uploaded his mind into a backup system when the Cybermen destroyed his original robot body, but he has never been able to construct another one as advanced as the one the Cybermen made for him. Over the centuries, he has become obsessed by his betrayal at their hands, and his subsequent mistrust and loathing of all aliens; as such, he is personally responsible for several technological breakthroughs which saved the Earth from invasion, and has almost single-handedly forged the Earth Empire from behind the scenes. He identifies his own needs with those of Earth, and believes that the deaths caused by the icaron drive are a small price to pay for understanding of a new technology which will keep the Earth -- and himself -- safe from harm. Now, after a thousand years of trying, he has finally located and stolen the TARDIS, and he begins to torture the Doctor, demanding that he reveal the time machine’s secrets. The Doctor realises that although Vaughn is capable of transmitting his mind into any robot manufactured by INITEC, he is obsessed with his own individuality and only allows himself to occupy one body at a time. He thus allows Vaughn into the TARDIS, but shuts the doors, sealing off the interior dimensions and preventing Vaughn from escaping into another robot body. He then cuts off Vaughn’s robot head, deactivating the rest of the body, but in memory of Pryce he chooses not to destroy Vaughn’s mind.

Powerless Friendless dies crashing the ship into the Undercity. The riots and murders will continue, but they won’t grow any worse; the Empire will still fall, but it will be replaced by something better, and the fall will be less bloody than it might have been. Chris fears that he may fall victim to the madness himself, and in any case, he and Roz have been placed on the list of known murderers by Rashid, who fears they will expose her corruption. As rogue Adjudicators they will be shot on sight if spotted anywhere in the Earth Empire. But now that he has his TARDIS back, the Doctor can offer a solution to both problems…