Shortly after leaving Benny and Jason’s wedding, the TARDIS is caught between two rare cosmic events -- a subspace infarction and a Vortex rupture -- and is destroyed. Roz and the Doctor are expelled onto the surface of Mars in the year 2157, during the Dalek invasion of the solar system. In this era, Mars has been terraformed and its atmosphere is breathable by humans, but the nights remain unbearably cold and the nearest city, Jacksonville, is 9,000 kilometres away.

While pondering their best move, the Doctor and Roz see a shuttle crash nearby, obviously having been shot down by. They investigate to find that the shuttle has crashed near a human expedition heading for the North Pole in search of supplies for Jacksonville, which has been cut off from trade due to the invasion. The somewhat ditzy lounge singer Carmen Santacosta has survived the shuttle crash, and three members of the expedition have survived -- leader Anthony McGuire, Marine Christine Madrigal, and scientist Vince Esteban. The Doctor is intrigued to learn that Esteban has been detecting magnetic storms at the North Pole, as Mars does not have a natural bipolar magnetic field. This is a puzzle for later, however; as the expedition’s transport has been knocked out by the shuttle crash. To survive the cold Martian nights, the Doctor suggests going underground into the abandoned Ice Warrior tunnels -- much to the displeasure of McGuire, who has personal reasons for hating the “Greenies”.

Chris ends up on Pluto’s twin Charon, where a group of stranded scientists have caused the subspace infarction with their attempts to use the technology of the old interstitial Transit system to break the invaders’ subspace blockade. At first the suspicious Rachel Anders believes that Chris is working with the invaders, as she doesn’t believe his claim to have survived the destruction of his ship in subspace. However, when Chris learns where he is and what the date is, he realises that the Daleks are about to attack Charon and destroy it utterly, killing everyone inside. Claiming to be an Adjudicator from the resistance base on Oberon, he convinces scientist Felice Delacroix to use the base’s tachyon telescope to prove his story, and she and Rachel see that the invaders are in fact heading straight for them. With minutes to go before the base is destroyed, the scientists try a new approach and successfully generate a subspace tunnel to the Ultima relay, outside the invaders’ blockade -- but the terminus of the stunnel is dragged off course back into the solar system. The scientists have no time to puzzle out the cause, however, as the invaders begin bombing Charon and the scientist are forced to evacuate to the stunnel’s unknown destination. Chris flees with them, but fears that by rescuing the doomed scientists, he may have changed history, broken the web of Time, and caused the Vortex rupture which contributed to the TARDIS’ destruction.

The Doctor leads McGuire’s expedition to the abandoned city of Ikk-ett-Saleth, and rescues McGuire from a trap set up to protect the civilian nest from unwanted intruders. The survivors of the expedition bed down for the night in the empty Martian homes, and the Doctor advises that Madrigal stand guard; Mars was supposedly abandoned by the Martians after the war with Earth, but there have been rumours amongst the human colonists that it has not been completely abandoned. This is in fact the case, but as yet the rest of the expedition is unaware that they have been spotted and followed by a group of Martian pilgrims led by Abbot Aklaar. The pilgrims are taking the legendary Sword of Tuburr to the North Pole, the holy lands of the god Oras, to break it as a symbolic refutation of their species’ warrior heritage. However, the young pilgrim Cleece is a former warrior who was adopted by a pacifist clan following the deaths of his parents -- and he still dreams of glory and the eradication of the human vermin...

The Doctor seems to be withdrawing into himself, and when Roz confronts him, he admits that the Vortex rupture which destroyed the TARDIS was most likely caused by a massive disruption to established history... such as the destruction of Earth. If his readings are accurate, the rupture originated at the Martian North Pole, and will take place within a week’s time. He and Roz soon have a more immediate problem to deal with, however, as Esteban is found dead shortly before Aklaar and his party make themselves known to the humans. McGuire instantly accuses them of Esteban’s murder; he loathes the Ice Warriors, blaming them for the terrorist attack in the Montreal monorail which left his wife and children dead.

Aklaar presents the Doctor with a holy relic forged from an Osirian star sapphire, proof that he and his party are not Warriors but are on a holy pilgrimage. Aklaar also informs McGuire that his people have launched no attacks on the human race since the war, and assures him that terrorism is anathema to the Ice Warriors’ code of honour. Taken aback by Aklaar’s understanding attitude, McGuire reluctantly accepts that his group has no choice but to join forces with the Martians if they are to survive the dangers of the underground tunnel system. However, as the pilgrimage continues, Roz realises that Cleece’s betrothed, Estaar, is in fact in love with the bookish, peaceful Sstaal -- and that the Doctor himself doesn’t trust the Martian pilgrims an inch. Unsure how the Doctor is dealing with the loss of the TARDIS, Roz remains silent when she begins to see ghostly images of the TARDIS floating through the tunnels.

Chris and the Charon scientists emerge from their stunnel near the mysterious Martian Sphinx, which was moved from the surface of the planet during the Thousand Day War. Leaving the other scientists safely in hiding, Chris, Rachel and Felice set off to explore, and soon find that they’re in an alien scientific base; however, the Martians lost the war because of their failure to discover subspace technology, and Chris fears that this may be a secret Dalek base. However, Rachel tracks down the subspace attractor which drew the stunnel off course, and is surprised to find it’s a glass pyramid filled with what appear to be Egyptian artefacts. This is not only evidence that Martian and Egyptian cultures were influenced by the same alien race, but that the Martians are in fact working on subspace technology after all -- and in some ways appear to be centuries ahead of what humanity can achieve.

Chris, Rachel and Felice are then captured by Ice Warriors and brought before Ice Lord Falaxyr, who tells them that they are in G’chun duss Ssethiissi, “The Cauldron of Sutekh.” In the face of the invasion, his people are preparing to leave Mars for the Nova Martia colony, as did all the other Martians when the war with Earth was lost. Falaxyr’s adjutant Draan shows the three to the city’s guest quarters, but Chris suspects that Falaxyr is lying to them. The Ice Warriors seem to have been expecting human guests, and the arrival of two quantum scientists in a scientific base which houses a giant subspace attractor seems too much of a coincidence for Chris’ liking. He convinces Felice and Rachel to play along while he tries to escape and find out what’s really going on. He’s right to worry; Falaxyr has in fact struck a deal with the Daleks, who have delayed the invasion of Mars to give him a chance to complete the so-called GodEngine. When Falaxyr’s scientists detected the subspace transmissions from Charon, Falaxyr told the Daleks about them, hoping that the additional pressure would drive the scientists on Charon to complete their work. Now that they are in his hands at last, he intends to force them to help him complete the GodEngine project -- but Chris is an extraneous complication, who must be disposed of.

The pilgrimage passes through the city of Sstee-ett-Haspar, abandoned for centuries following a plague; the plague has burned itself out, but the city has reverted to a natural wilderness, complete with predators and other nasty surprises. Madrigal is killed by a plasma blast from a rock-snake, and when Roz examines her weapon she discovers that it was sabotaged, leaving her defenceless. The other expedition members pass through safely and finally reach their destination, the nest at G’chun duss Ssethiissi -- but the Doctor notes that all of the trisilicate has been mined out of the surrounding tunnels, and Aklaar becomes disturbed when they arrive at their destination only to find that the city is shielded by the hull of an Osirian WarScarab. Why has military technology been used to protect what Aklaar believed to be a religious nest?

Roz has become suspicious of Santacosta, and her fears are confirmed when she spots Santacosta slipping away from the others and using a secret communicator. When she confronts Santacosta, the “singer” defends herself with moves known only to the Adjudicators. She strikes Roz with what should be a fatal blow, but Roz protects herself with a technique unknown in this century and follows Santacosta back to the hull of the Scarab. There, Aklaar is taken aback when a party of Ice Warriors opens the hull of the Scarab from the inside -- but Santacosta then throws a transit-web terminus through the hull, revealing that the Adjudicators knew of the subspace experiments at the North Pole and of Aklaar’s pilgrimage. Something blocked their attempts to generate a stunnel through to the Martian base, and Santacosta thus infiltrated McGuire’s expedition, believing that he would encounter Aklaar and that the pilgrims would be able to get past the source of the interference. She killed Esteban because he sympathised with the Ice Warriors and was suspected of being a member of the Martian Axis, and Madrigal simply because a trained Marine would get in the way of what Santacosta had to do here.

The transit web activates, generating a stunnel through which a squadron of trained Adjudicators will pour through, seize whatever the Martians have been working on, and turn it against the invaders. However, a ghost-TARDIS appears in the corridor and begins to float towards the stunnel. Realising the implications, the Doctor throws Aklaar’s holy relic into the stunnel. It is the hull of the WarScarab which blocked the Adjudicators’ attempts to generate a stunnel into the Martian base, and the Osirian star sapphire from which the relic was carved has the same effect, shutting down the transit web. The ghost-TARDIS fades away at the same time, and the Doctor reveals that if it had intersected the stunnel, the resulting subspace infarction would have killed them all as well as destroying the adjudication base on Oberon. When nobody is looking, he pockets the transit-web.

Things are not going well for the Ice Warriors at G’chun duss Ssethiissi. Falaxyr has insisted that Chris be treated as an honourable opponent rather than killed outright, but Chris has taken advantage of his freedom to mix up chemical bombs from his drugged food and the supplies from the survival kit he took from the TARDIS. When Draan arrives to take him for execution, Chris uses his makeshift weapons to escape, and spends the next two days one step ahead of the Warriors, planting bombs in strategic locations in the Ice Warrior base. In the meantime, Falaxyr decides to continue with the GodEngine project, and has Technician Yeess take Felice and Rachel to the Brain-Rack in order to condition them to obey Falaxyr without question. Yeess becomes uncomfortable with his orders when he learns that Rachel’s brother Michael is a hero of the Martian race. He used to be part of the UN peacekeeping force on Mars, and then joined the Martian Axis, but separated from them when he realised they were using the cause of Martian freedom as an excuse to justify their own terrorist activities. Michael then accompanied the evacuating Martians to Cluut-ett-Pictar, where he died defending the Martians from an Arcturan attack force. Nevertheless, despite his respect for her brother, Yeess carries out his orders and processes both Rachel and Felice, conditioning them to finish work on the GodEngine without question.

The new arrivals are imprisoned in double cells. Roz, placed with Santacosta, admits that she’s an Adjudicator from the future. McGuire and Sstaal are placed together, and McGuire finally lets go of his hatred when Sstaal explains that the Martian Axis, the terrorists who killed his family, were using the Martians’ name for their own political agenda; the real Martians were unable to respond, as doing so would have betrayed their continued presence on Mars to the still-hostile human race. Estaar informs the horrified Cleece that she intends to request a Sundering of their betrothal in order to marry Sstaal, the father of her children. The Doctor is locked up with Aklaar, and comes to believe that, though Aklaar is clearly surprised by the presence of the military here, he knows more about what’s going on than he’s admitted.

Chris sets off his bombs, throwing the base into confusion. Roz and Santacosta break out of their cell and join forces with Chris. They manage to break Rachel free of her conditioning, but are unable to prevent Felice from finishing her work and completing the GodEngine. Falaxyr summons his other prisoners to witness the culmination of a plan 70 years in the making, and forces Aklaar to admit his true identity. Before he renounced his title and joined the religious order, he was known as Abrasaar, the Butcher of Viis Claar; he and Falaxyr are the only two survivors of the Eight-Point Table, the leaders of the Martian military who launched the futile war against Earth. Unlike Falaxyr, Aklaar regrets his past and has tried to atone for his crimes, but now Falaxyr has tricked him into bringing the Sword of Tuburr, the last component necessary to complete the GodEngine.

When the Martians realised that the humans had access to subspace technology, they attempted to adapt the Osirian technology abandoned on Mars and create weapons with it. The GodEngine is the culmination of that project; when tuned properly, it can manipulate the subspace manifold around stars, turning them into subspace plasma projectors. When the Osirians imprisoned Sutekh on Earth, they set up the controls for the force field on Mars, because their technology would only work properly here; both Mars and Phaester Osiris have no natural bipolar magnetic field, and the Osirians’ technology is based on magnetic monopoles. Believing that the GodEngine will only work on Mars, Falaxyr has struck a deal with the Daleks to let the Martians reclaim their homeworld once Earth is destroyed -- but the Doctor realises that this is why the Daleks are really mining out the magnetic core of the Earth, so they can take the GodEngine themselves and install it on Earth.

Cleece rejects his pacifist teachings and turns over the Sword of Tuburr to Falaxyr, and since Draan has still failed to capture Chris, Falaxyr makes Cleece his new adjutant. Aklaar challenges Falaxyr to a duel to prevent him from activating the GodEngine, but Falaxyr wins and kills him. He then prepares to use the GodEngine to destroy the human colony at Jacksonville, ignoring Rachel’s attempts to warn him that the weapon can’t possibly be fine-tuned to that degree; if he tries to use it, he will destroy most of Mars. As the GodEngine powers up, however, a host of ghostly TARDISes float into the room, and in the confusion, Roz, Chris and Santacosta create a distraction, enabling the Doctor to throw Santacosta’s transit-web onto the GodEngine. The interaction of subspace fields causes the GodEngine to overload, and the power relays on the surface of the planet explode. Draan tries to kill Falaxyr for his failure, but Cleece kills Draan -- and Sstaal then kills Cleece, revealing that Cleece’s parents were actually of the religious caste all along and that Aklaar never told Cleece the truth for fear it would traumatise him.

As Falaxyr flees, the power flooding through the GodEngine reaches critical -- and the GodEngine vanishes, replaced by a fully functioning TARDIS. Since the Doctor destroyed the GodEngine before it could destroy Mars or Earth, history was never changed and the Vortex rupture never occurred; thus, the potential futures which took the form of ghostly TARDISes have been resolved, and the extra energy released by the destruction of the GodEngine has brought the TARDIS back into existence. Falaxyr tries to escape in a shuttle, but is shot down by Daleks enforcing the blockade.