In the 30th century, the Earth Empire is contracting and plans are being made to decolonise the colony world of Solos. The militaristic Marshal and other human soldiers, known as Overlords, rule it from Skybase One. The Marshal opposes the decolonisation plans outlined to him by Administrator sent from Earth, and is also obsessed with eradicating the Mutants or Mutts that have sprung up on the planet below. The Solonians themselves are a tribal people, split between those who actively oppose the occupation, such as Ky, and those like Varan who collaborate with the imperialists. Indeed, the Marshal and Varan ensure the Administrator is murdered before he can confirm to Ky and other tribal chiefs that the Earth Empire is indeed withdrawing from Solos.
The Third Doctor and Jo arrive on Skybase One, their TARDIS having been transported there by the Time Lords. They have with them a message box which will only open for an intended recipient – and that is not the Marshal or his entourage – but seems to be for Ky, who has been framed for the murder of the Administrator. Jo and Ky flee to the surface of Solos, which seems to be poisonous to humans during daylight hours, and this affects Jo quite soon. Ky saves her with a stolen oxygen mask. The Doctor learns from the Marshal and his chief scientist Jaeger that they are involved in an experiment using rocket barrages to terraform Solos, making the air breathable to humans, regardless of the cost to indigenous life. They continue to bombard the surface with ever more deadly rockets.
Varan by now has discovered the Marshal’s treachery and events make him an outlaw on Skybase. The Doctor makes contact and together they persuade Stubbs and Cotton, the most senior soldiers to the Marshal, that much is wrong on Skybase. He then flees to Solos with Varan, and at the thaesium mine where Ky and Jo are hiding he encounters many Mutts, who are not as hostile as they first appeared. The Doctor passes the message box to Ky, and it opens to reveal ancient tablets and etchings which are written in the language of the Old Ones of the planet. Help in avoiding poisonous gas released by the Marshal is provided by a fugitive human scientist, Sondergaard, who lives in the caves and knows much about Solonian anthropology. Sondergaard explains he tried to inform Earth Control about the Marshal's evil, but he was prevented and forced to flee to the caves, where the radiation seems to have affected him. He interprets the contents of the box as a “lost Solos Book of Genesis”, and the Doctor then calculates a Solonian year to be equivalent to two thousand human years, with natural changes in the population every five hundred years within the cycle. Investigating a more radioactive part of the caves, the Doctor thus deduces the Mutant phase is a natural part of the Solonian racial life-cycle.
Varan has by now become a Mutt himself, the transformation beginning with his hand. He hides this and leads a Solonian attack on the Skybase which results in his death and those of many of his warriors. On Skybase Jo, Ky, Stubbs and Cotton are captured by the Marshal, and Stubbs is killed in a failed escape attempt. The Doctor meanwhile has returned to the Skybase – without Sondergaard, who seems too weak following the radiation contamination. He instead returns to the caves to communicate with the Mutants and explain to them the changes in their metabolisms are natural and not to be feared.
The Doctor is now back on Skybase and surmises the Marshal to be mad. It becomes clear that the Earth Government has now dispatched an Investigator to look into the strange events on Solos. The Marshal’s rocket attacks have not terraformed the planet, but they have left a hideous environmental impact and he knows he must clean this up or face problems when the Investigator arrives. Under duress the Doctor uses Jaeger’s technology to conduct a rapid decontamination of the planet’s surface. The Investigator arrives and demands answers, but is given more lies by the Marshal, supported by the Doctor, who fears Jo will be killed if he does not co-operate. Luckily Jo, Ky and Cotton have escaped their detention and arrive in time to help the Investigator see the truth of the situation on Solos and the crimes of the Marshal and Jaeger. The Doctor accuses them of "the most brutal and callous series of crimes against a defenseless people it's ever been my misfortunate to encounter." Sondergaard now reaches the Skybase with some Mutants, one of whom scares the Investigator enough that he accepts the Marshal’s analysis that the creatures should be killed.
Ky now begins a process of mutation, but it is accelerated beyond the Mutant phase so that he emerges as a radiant angel-like super-being. He communicates with thought transference, can float and can move through whole walls. Dispensing justice, Ky eradicates the Marshal. Jaeger has been killed too and the Investigator now makes sense of the situation. Sondergaard and Cotton elect to stay on Solos to see the other Solonians go through the mutation process, while Jo and the Doctor slip away, their mission from the Time Lords complete.