The Doctor and Jo visit the Master, now held in captivity on a small island prison, after being captured by UNIT (at the conclusion of The Daemons). The Master is being held indefinitely and is the only prisoner. He is watched by CCTV and the island is patrolled by armed guards, trained to resist the Master's hypnotic powers, and even protected by minefields. He claims to have reformed but refuses to reveal the location of his TARDIS.
As they depart, the old-school patriotic governor, Colonel Trenchard, tells them that some ships have been mysteriously disappearing. The Doctor cannot resist investigating and he and Jo are soon attacked, while examining a Sea Fort, by an underwater Silurian. This man-sized bipedal lizard is called a 'Sea Devil' by a crew member who's been driven half mad. They escape to the nearby naval base, HMS Seaspite run by the efficient Captain John Hart; despite the Doctor's eccentric behaviour (such as claiming to have known Nelson personally), an alliance forms. Hart is in charge of the adaptation of the sea fort for use as a SONAR testing station.
The Doctor meanwhile discovers that the Master, assisted by a misguided Trenchard, is stealing electrical equipment from the naval base to build a machine that will control the Sea Devils. The evil Time Lord intends to use the reptiles as an army to enable him to conquer the planet, and he begins by using the machine to summon some of them from the sea. Soon, however, a battle for the prison ensues, during which Trenchard, who had believed he was aiding his country against enemy agents, is killed. The Doctor and Jo are forced to flee to HMS Seaspite, where Hart tells them a naval submarine has disappeared. The crew prepare to battle the sea devils. The Doctor investigates in a submarine bell and is seized by the Sea Devils, who take him to their leader.
The Doctor enters the Sea Devil's base and tries to encourage peaceful negotiation, recalling how he had failed to broker an agreement between mankind and the Silurians, but matters are left unresolved when the base is attacked by depth charges. This attack has been ordered by a gluttonous and short-sighted politician, Robert Walker, who has arrived at HMS Seaspite to take control of the situation and is intent on repeating UNIT's actions on Wenley Moor: blowing up the creatures, but this time with nuclear weapons. Hart and Jo are opposed to the attack but at least it allows the Doctor cover to flee, even if he has failed in his initial attempt to sue for peace.
The Doctor persuades Walker to allow him a final attempt at negotiation, but in the meantime the Sea Devils capture the naval base. They have been inspired to such actions by the Master, who still wishes to instigate a war. The Master then forces the Doctor to help build a machine to revive Sea Devil colonies all over the world. Returning to the Sea Devil base the Master activates the device, whereupon the Sea Devils imprison both Time Lords, as they are now both equally useless to them. However, The Doctor has sabotaged the machine and he and the Master escape the base using escape equipment from the captured submarine.
As they are rescued, massive power feedback from the sabotaged machine destroys the Sea Devil colony before the military attack can begin. As he has done before, the Master is able to escape capture (this time by faking a heart attack and hijacking a rescue hovercraft) and flees the scene.