A team of geologists and paleontologists is attacked while exploring a newly discovered cave system. The sole survivor, Professor Kyle, calls in a paramilitary squadron to help her. Under the command of Lieutenant Scott, the squad prepares to enter the caves while Trooper Walters sets up a scanner which will detect any mammalian life within range. The scan comes up negative -- Kyle's entire team has been killed. Walters and Trooper Snyder remain on watch outside while Scott leads his team into the caves, but apart from strange intermittent flares the scanner shows no sign of the two black-clad humanoid figures who are stalking the squadron's every move.

The Doctor finds Adric moping in his room, depressed that nobody wants to spend time with him. Their discussion rapidly deteriorates into a shouting match, and Adric decides that he wants to return to E-Space and sets about calculating a safe path back through the CVEs. The TARDIS materializes in a cave system on Earth in the year 2526 AD, and the Doctor storms out, leaving Adric on his own. Tegan goes to talk sense into the Doctor while Adric admits to Nyssa that he let the argument go too far. He decides to finish his calculations in any case, just to show he can do it, while Nyssa helps Tegan to calm down the Doctor.

Kyle admits to Scott that their expedition was plagued with problems from the beginning -- as if someone wanted them to fail all along. The lighting system in the cave suddenly fails, and in the confusion Trooper Bane stumbles and dislocates her shoulder. She is sent back to the surface with another trooper as her escort; meanwhile, Walters contacts Scott to report that three figures have just appeared on his scanner, near the cavern where Kyle's team was attacked -- and according to the scan, one of the new arrivals is an alien with two hearts...

The wounded party seems to be making little progress, and Snyder enters the caves to find and guide them back. But as Walters watches, the scanner flares again, and the lights indicating Snyder's and the others' life signs go out. As he frantically attempts to contact Snyder, the two figures in black stand over a bubbling puddle of organic slime which is all that remains of her. Walters reports to Scott, who sends Sergeant Mitchell and two troopers back to investigate. But Walters hears them die screaming while reporting the presence of the two figures -- who still don't appear on his scanner.

The Doctor eventually calms down and agrees to discuss things rationally with Adric. Nyssa notices large fossilised bones in the cave walls, and the Doctor and Tegan tell her about dinosaurs and the meteor collision which wiped them from the face of the Earth 65 million years ago. They explore further and find the equipment used by Kyle's expedition, but are then confronted and held at gunpoint by Scott's troopers. Scott demands to know where they've hidden the bodies of Kyle's teammates, and when Kyle points out a recent rockfall, Scott forces the Doctor, Tegan and Nyssa to clear it away, believing that the bodies will be beneath. The two figures in black rush back to the cavern; meanwhile, Adric hears a strange signal coming from the console but has no idea what it means.

The troopers concentrate their fire and damage one of the androids, and the androids retreat under cover but keep the exit blocked. The power packs in the troopers' guns are running low; they must resolve this quickly or they'll all end up dead. Adric emerges from the TARDIS to tell the Doctor about the signal he's picking up, but the others manage to warn him of the danger in time and he takes cover. The Doctor then advises Scott to fire upon the hatchway. The androids will be faced with two conflicting priorities -- protect the hatch at all costs while protecting themselves -- and the confusion in their logic circuits will cause them to start making mistakes. The plan works perfectly, and Adric helps to distract an android by throwing a boulder at it at just the right time. Both androids are destroyed, and the Cybermen, concluding that the device is lost to them, decide to explode the bomb prematurely...

Celebrations are curtailed when Nyssa and the Doctor study the remains of an android and determine that it was equipped with a transmitter; whoever built the hatch now knows that its guardians have been destroyed. The Doctor decides to open the hatch and find out what's so important, but when he does so he finds a bomb capable of destroying the Earth -- and an arming procedure has been activated. At first he believes that he's triggered the arming procedure by opening the hatchway, but when Scott tries to contact Walters his radio pulses with interference in the same pattern as the arming procedure. The Doctor realizes that the bomb is being activated by remote control and is able to use the TARDIS to jam the transmission. As the Cybermen increase power, trying to break through the interference, the Doctor and Adric defuse the bomb, abandoning methodical procedure for blind instinct and succeeding just in time.

The Cybermen, believing that their technology is too advanced for humans to outwit, replay the androids' transmission of the battle in the caves to determine who has betrayed them. This time, the Cyber Leader spots the TARDIS in the background and recognizes it from historical archives. Once again the Doctor has arrived to thwart their plans, and this time he must be found and killed.

The Doctor, wondering why a bomb was used and not a missile, traces the arming signal to a sector in deep space. Scott insists upon accompanying the Doctor to defend his planet, and the Doctor reluctantly agrees to let his squad come along. As Tegan leads the squad into the TARDIS to freshen up, the Doctor thanks Adric for his help in defeating the androids and defusing the bomb, and he and Adric apologise to each other for their earlier blow-up. The TARDIS materializes on a cargo freighter in deep space; this may only be a relay point for the signal with an innocent crew, so the Doctor decides to go out for a recce before letting Scott's squad loose. Friends again, he allows Adric to accompany him...

Captain Briggs is in a foul mood, as she's been delayed by bureaucrats and is in danger of missing her schedule and losing her bonus. Earth's on red alert due to an interstellar conference, and if there's one hint of trouble the ship will be delayed for months. Thus neither Briggs nor any of her crew have mentioned the disappearance of three crewmen within the past two weeks... She now has security clearance straight through to Earth, and enters the transponder code into the navigational computer, certain that her bonus is now secure. The by-the-book security officer Ringway is irritated by the captain's attitude and by her and her first officer Berger constantly running down his earnestness. He sets off to check on the security patrols as the ship enters warp drive. Meanwhile, the Cyber Leader receives a report from a traitor, reporting the unrest caused by the disappearances. He advises the traitor to send patrols into the cargo hold -- scapegoats have just arrived.

Ringway reports to Briggs, who orders him to bring the Doctor and Adric to the bridge for questioning. Meanwhile, the Cyber Leader decides that the time has come to activate his guard and seize control of the ship. As the Doctor and Adric try to convince the incredulous Briggs of their story, the computer reports a power loss and traces it to the hold. As Ringway passes out weapons to the crew, the power loss worsens, but despite the danger Briggs refuses to pull out of warp drive; if she deviates from her security-cleared course she'll be stopped, and the delay will cost her both her bonus and hefty fines.

Nyssa detects a powerful electromagnetic field as the Cyberman patrol is activated, and after the field dies down Scott decides to lead his troops out to investigate. Tegan demands to be allowed to accompany them, while Nyssa and Kyle remain in the TARDIS. Scott gives Nyssa a communicator so she can contact him if the Doctor returns. Tegan soon has second thoughts as she accompanies the patrol through the immense cargo hold of the freighter.

As Briggs and Berger struggle to hold the ship on course, Adric points out to the Doctor that the bomb was probably planted on Earth because a missile wouldn't get through the extra security. The power returns to normal, but this is because it's no longer needed; a full complement of Cybermen has been awoken and they mercilessly slaughter their way through the freighter's crew. Ringway returns to the bridge -- where he holds the others at gunpoint, and reveals that he is working for the Cybermen. The Doctor manages to work the Cybermen's weakness to gold into the conversation, and tries to distract Ringway while Adric removes his golden star badge. Ringway spots him doing so, but Berger hides while Ringway is distracted, and when he notices she's gone Briggs and the Doctor are able to surprise and overpower him. Berger shuts the bridge's bulkheads just as the Cybermen arrive, having killed the rest of the crew. Briggs believes that the bulkheads will be able to hold off the few Cybermen on board until Adric and the Doctor point out that she's carrying 15,000 silos in the hold. Suddenly, she realizes what her cargo really is...

Scott's patrol finds the bodies of the ship's crew and Tegan spots two Cybermen on guard nearby. The troopers concentrate their fire and bring down the Cybermen, and Tegan risks her life to grab one of the Cyber-guns and destroy one of the Cybermen. The other manages to crawl up to the command decks, leaking hydraulic fluid, and when it collapses in front of the Cyber Leader he concludes erroneously that Ringway lied about the number of crewman aboard the ship. He orders reinforcements to be activated and orders that the Doctor be taken alive and made to suffer for the Cybermen's past defeats.

The Cybermen lock off the ship's navigational computer and connect a control mechanism to it. The freighter is now a flying bomb; by the time Earth authorities realize it isn't going to stop it will have crashed into the planet, doing the work of the bomb the Doctor defused earlier. The Cyber Leader reveals that the conference being held on Earth is meant to form an alliance of governments against the Cybermen; by destroying the entire planet to get at the conference, the Cybermen will strike a decisive psychological blow against their enemies. The squad on board the freighter was originally intended to land and kill any survivors; now they will be abandoned and the Cyber Leader will join a secondary squadron to complete his task.

Unable to find Tegan, Scott and his soldiers return to the TARDIS, but once there they are attacked by two Cybermen who kill one of the soldiers and follow the others into the TARDIS. Scott and his two surviving troopers destroy both Cybermen but Kyle is killed in the fight. Scott and the troopers then leave again, now armed with two Cyber guns.

Tegan is captured and taken to the bridge, where the Cyber Leader, realizing that the Doctor has affection for her, demonstrates the inefficiency of emotions by threatening to kill her. When the Doctor stops him, the Cyber Leader concludes that by threatening Tegan's life he can force the Doctor to obey him. The regenerated Cybermen evacuate the ship, apart from two guards who remain on the bridge to prevent Briggs and Berger from interfering. The Cyber Lieutenant reports to the main fleet, while the Cyber Leader orders the Doctor to pilot him to safety in the TARDIS. Since the Leader already has Tegan as a hostage, he orders that Adric remain on board the freighter -- and when he threatens to kill Tegan unless they obey, Adric urges the Doctor to let him stay and find his own way to safety. The Doctor has no choice...

Nyssa is shocked when the Doctor and Tegan march into the TARDIS under armed guard by the Leader and his Lieutenant. While the Lieutenant explores the corridors of the TARDIS, the Leader forces the Doctor to lock onto the freighter's co-ordinates and follow it to Earth. But the Lieutenant has left the revival machinery active, and more Cybermen awaken from hibernation and automatically march on the bridge.

Scott destroys both Cybermen on the bridge, and he and his men hold off the attacking Cybermen while Adric and Berger try to solve the three logic codes which prevent them from accessing navigational control. They successfully crack the first code, and when they enter it into the computer, the partial warp-drive override causes the freighter to begin travelling backwards in Time. However, this just increases the threat; the ship is still locked onto the same spatial co-ordinates, and if it collides with Earth then history will be changed and Earth will never have existed as they know it. Adric solves the second code, bringing the freighter out of warp drive -- but they have already entered Earth's solar system. The others, realizing that there isn't time to crack the third code, abandon ship in the escape pod, but Adric refuses to give up and leaps out of the pod just as the bulkhead is closing. He is unaware that one of the Cybermen has survived the battle with Scott's troopers; and as Adric struggles with the final code, the mortally wounded Cyberman crawls towards the bridge to complete its mission...

Just as all seems lost the Doctor reveals that the freighter has gone back 65 million years; its collision with Earth will in fact be the impact which wipes out the dinosaurs. Scott radios the Doctor to tell him that everybody but Adric has escaped, and the Cyber Leader prepares to kill the Doctor; but the Doctor disables him by crumbling Adric's golden star badge into his chest unit. The damaged Leader fires its weapon at random, damaging the TARDIS console before the Doctor is able to pry the gun from his hands and destroy him. The Lieutenant returns to the console room, but Nyssa guns him down as the Doctor struggles to bypass the damage to the console and materialize on board the freighter. Meanwhile, Adric solves the last code -- just as the wounded Cyberman arrives and destroys the navigational computer. The Cyberman collapses, dead, and Adric -- realizing that he'll never know now if he was right -- clutches his dead brother's marsh-reed belt in his hands as the image of Earth grows larger in the viewscreen...