Thanks to the Webster Corporation, NASA can finally afford to send a manned mission to Mars -- but with Leo Webster pulling the strings they have had no choice but to allow Leo's son Paul and 17-year-old niece Tanya to join the mission team. While the command module Ares One remains in orbit, Paul, Tanya, Commander Lee Forbes and pilot Susan Roberts take the last stage of the journey in the landing module, the Argosy. There are a few uncomfortable moments during the descent, as the retro-rockets momentarily fail to fire, and a dust storm makes it difficult for the landing radar to get a lock on the ground. Fortunately, these turn out to be minor problems soon overcome, and the Argosy makes a picture-perfect touchdown on the night side of Mars... less than half a mile from the anomaly which Webster wants his team to investigate.

The Doctor promised Peri a tour of an alien world, and the TARDIS has materialised somewhere with a breathable but nitrogen-rich atmosphere. This could be ideal for certain forms of plant life, and the botanist in Peri is eager to explore. They seem to be inside a building with green walls like organic shell, and as they explore further they find doors operated by handplates. The Doctor is at first unsure what the operating principles are, or why there are alcoves containing ice blocks near each door. Peri, however, thinks she can discern something beneath the nearly opaque surface of the ice, and the Doctor theorises that they may contain machinery used to operate the doors. He's still not sure where they are, but it has the feel of an ancient building, like a church or a castle. He and Peri reach a door unlike any of the others, which may be an airlock of some kind, and which the Doctor finds more difficult to open; nevertheless, he decides to try, hoping that the other side will offer some clue as to where they are.

The dust is settling around Argosy, and when the floodlights go on they illuminate the anomaly, which appears to be a rather large hill. It doesn't look important enough to justify aking this the landing site, but Webster insisted, and he's the one paying for the mission. As the others unpack their survey equipment, Forbes steps outside the lander for reconnaissance, becoming the first man to set foot on Mars since the Mars Probe fiasco. Just as he comes within sight of the anomaly, his communications equipment cuts out in the midst of a startled exclamation; however, he is all right, and when he makes it back to the lander he ignores the others' worried questions, instead tapping at the controls to see if he can raise Mission Control. He cannot do so, and Tanya finds that the carrier signal has been deactivated somehow. Forbes tells them that the anomaly is not a natural phenomenon, but a giant building made of organic green shell, and orders Roberts to come with him while Paul and Tanya continue to unpack the excursion gear; once they've found an entrance to the anomaly they can run a docking tube from the Argosy. As they approach, however, Forbes first makes sure that they aren't transmitting back to the Lander, and then tells Roberts something she has to know about the Brookings Report.

The Doctor realises that the door plates are operated empathically, and that the doors will only open for those whose intentions are honourable. The airlock opens from the ther side, admitting Forbes and Roberts, who are extremely surprised to encounter the Doctor and Peri. The Doctor promises to explain their presence, and offers to show Forbes around the building; Peri, however, is starting to feel the cold this close to the exterior of the building, and Roberts agrees to take her back through the docking tube to the landing module for an extra survival suit. There, Tanya and Paul are also surprised by Peri's arrival. They have finished unpacking -- but Tanya doesn't know that Paul has pocketed something from the geology kits, which he feels might be useful later...

Forbes realises that the Doctor is avoiding the central room in the structure, and the Doctor admits that he prefers to explore the outlying regions of the structure rather than following its architects to guide him somewhere he may not want to go. Nevertheless, Forbes insists upon investigating, and the Doctor thus operates the doorplate. The room beyond appears to be a warrior's tomb, a huge central chamber surrounded by alcoves containing ice blocks -- but just as the Doctor realises that he too can see something buried in the ice, he and Forbes realise that the room is starting to warm up. Their arrival has tripped some sort of mechanism, and as the figures in the ice blocks start to move, the Doctor finally realises where they are and what is happening. Roberts calls, demanding to know what's happening, and as the Doctor urges everyone to keep calm and stay where they are, the ice blocks split open... and living Ice Warriors emerge.

The Doctor and Forbes are taken prisoner by Lord Zzaal, who at first seems to suspect them of tomb robbing; however, he concedes that the doors would not have opened if their intentions had not been honourable. The Doctor warns that one man's good intentions may not be enough, and is proven right when the frightened Roberts enters and points a weapon at the Ice Warriors, telling them to back off. Before anyone can stop him, Zzaal's adjutant Sstast guns her down with his built-in sonic gun, fatally injuring her -- and the furious Doctor points out that she was bluffing, and trying to hold them at bay with a spectographer. Zzaal orders his troops to take her to their medical facilities, and do what they can to ease her pain; in the meantime, he will send Sstast to the landing module to collect the other humans.

Paul is surprised to learn that Leo Webster requested that the mission investigate the anomaly, and becomes suspicious when Tanya tells her that Paul is the head of Webster corporation's defense division. Paul admits that they've known all along that the anomaly was an alien artefact. The first probes to Mars brought back more than just soil samples; they found technological debris and fragments of organic shell, containing alien DNA. Now that they've made contact, however, Paul is unable to get word back to Earth, due to the communications blackout. Peri, however, points out that the aliens weren't actually awake at the time they lost the carrier signal, and when Tanya investigates further she realises that someone has assigned a new password to the systems. Either Roberts or Forbes deliberately cut them off from Earth.

Zzaal explains that this is the tomb of Izdal, the greatest warrior of their race. When their planet's temperature and atmosphere began to change, Izdal made the ultimate sacrifice to ensure that his people would evacuate Mars and thus survive the coming of the Red Dawn. Zzaal was the leader of Izdal's personal guard, and he and his men entered cryogenic suspension to continue protecting his resting place... and, Zzaal admits, for another reason. Life was first beginning to develop on Earth when the Martians evacuated, and although they did not have the opportunity to exploit their neighbours' resources, they knew that an opportunity to make a trade agreement would one day arise. This is why the doors of the tomb will only open to those with good intentions -- but just because one man is honourable, this doesn't guarantee that the others will follow his lead, or that tragic misunderstandings will not occur. Roberts dies without regaining consciousness, but Zzaal promises that she will be buried as a warrior should be.

Sstast arrives at the Argosy, but before Tanya and Peri realise what he's doing, Paul opens up an oxygen cylinder in Sstast's face. Unable to cope with the change in atmosphere, Sstast is unable to protect himself when Paul hits him in the head with the cylinder, knocking him out. Paul removes Sstast's built-in sonic gun, which Tanya seems to understand instinctively, and when the Doctor calls them to tell them that Sstast is on his way, Paul informs the furious Zzaal that Sstast will be held prisoner to ensure that the others keep away. He cuts off the protesting Doctor, and when Peri also protests, he holds her at gunpoint with Sstast's weapon. Tanya knows that the Ice Warriors will regard this as an act of war, but Paul informs her that if an interplanetary war breaks out, then Webster Corporation will be ideally placed to trade to both sides -- for this warrior is the final piece of the puzzle they have been assembling. The technology is available to create hybrid humans with alien DNA compounds; with Sstast as their prisoner, Webster Corporation will be able to manufacture the first Earth Warriors...

Zzaal accuses the Doctor and Forbes of keeping him occupied while their associate took Sstast prisoner. The Doctor tries to calm him down, but Zzaal refuses to listen and sends his warriors Zizmar and Sskaan to rescue Sstast -- or give him an honourable death by destroying the Argosy and all aboard. As the Warriors start to burn through the hatchway, Paul orders Tanya to start the launch procedure, and when she refuses, he does so himself. Tanya has no choice but to complete the sequence, and the Argosy takes off, separating Peri from the Doctor, leaving Forbes stranded and incinerating Zizmar and Sskaan. Zzaal refuses to permit his enemies to escape with Sstast as their prisoner, and orders his troops to activate the tomb's defense systems. Ice Warriors defend themselves, even in death. The Doctor begs Zzaal to see reason and not to kill the innocent to save Sstast's honour, but Zzaal ignores him, and the Doctor and Forbes watch helplessly as the Ice Warriors fire their first missiles at the Argosy...

Tanya and Peri try to free Sstast from his bonds, but Paul holds them off at gunpoint, refusing to stand down. Before he realises what is happening, however, they are struck by the Ice Warriors' missiles, and the Argosy is seriously damaged and starts to spiral. As Paul begins to panic, Sstast regains consciousness, breaks free of his loosened bonds and knocks Paul out. The Argosy is still spiralling, however, and Tanya isn't certain whether she can make orbit -- or land safely.

A second missile will destroy the Argosy completely, but as Zzaal prepares to give the order, the Doctor rewires Forbes' communicator and changes the output frequency. The sonic signal it gives off debilitates the Ice Warriors, but rather than force them to stand down their weapons systems, the Doctor switches off his own makeshift weapon and hands it over to Zzaal. After a moment, Zzaal returns it to Forbes and agrees to let them contact their comrades. The Argosy's situation appears desperate, but Zzaal informs the humans that the sonic strike has affected their instruments -- they may be in better shape than they think, but they will have to try to make a visual landing without instruments. Assuming that the heat shield -- which was designed for a single descent into the atmosphere, not two -- will let them. Sstast, Tanya and Peri work together to land the vessel; while Peri monitors the readings, Tanya operates the retro-rockets while Sstast looks out of the window and tells her when the module is oriented towards the surface. They must get the timing precisely right; they need the retro-rockets to slow their descent, but have been venting fuel rapidly.

At first it appears that the descending module is going to crash right into the centre of the tomb, but as it approaches the surface, the dust storm which caused them trouble on their initial descent causes it to drift off course. As it nears the surface, Tanya fires the retro-rockets, and although they run out of fuel before they hit, they have slowed their descent enough to survive.

The Doctor takes Roberts' survival suit and accompanies Forbes and Zzaal onto the surface of Mars -- a world too cold for even the Ice Warriors, with an atmosphere far too thin to support life. They arrive at the lander, which is no longer capable of flight, to find that Sstast now intends to execute all of his prisoners, including Tanya and Peri. The Doctor begs Zzaal to show mercy and let the human legal system deal with Paul, and Zzaal agrees to do so; there is dignity in forgiveness, just as there is honour in revenge. They will be taken back to the tomb, and allowed to use the Ice Warriors' ship to rejoin Ares One in orbit.

As they enter the tomb, Tanya realises that she somehow knows it to be the tomb of Izdal, but is unsure where she heard the name. Paul's cocky attitude has returned, and he approaches the tomb itself, apparently to scrape the ice away and look at Izdal's terribly scarred and burned body... but as the Ice Warriors move forward to stop him, he pulls out the blasting charge which he took from the geology kit earlier. Its remote detonator operates by ultrasound, and if the Ice Warriors try to shoot him down the bomb will go off and destroy Izdal's tomb. Paul intends to leave Mars in the Ice Warriors' ship, but on his own terms. He sets the charge by the tomb and takes the remote detonator with him; it only has a limited range, but he intends to be safely on his way before he returns it. In order to get him far enough away from the tomb to act, Zzaal agrees to show him to their sonic tank, an armoured vehicle which Paul is only too happy to take back to Earth with him. He takes the Doctor and Tanya with him as hostages, but the Doctor points out that Paul will be unable to pilot the Martian tank. Paul, however, intends to let Tanya operate it -- and he's had enough of the Doctor's insults. Before Tanya or the Doctor can do anything, Paul presses his stolen sonic gun up against the Doctor's head...

After a tense moment, Paul lowers the weapon, satisfied that the Doctor will give him no further trouble. They enter the tank, and much to Tanya's surprise, she finds the controls systems oddly familiar. Paul throws the detonator out of the tank as promised, but despite the danger, the Ice Warrior Razzburr volunteers to try operating the emergency cut-out in the main engine housing. Tanya, however, has worked out how to power up the engines, and just as Razzbur reports back that he's located the cut-out, the engines fire up and he is incinerated. The tank sets off across the plain... and grinds to a halt as the cut-out finally kicks in. Unfortunately, although Paul is unable to reach safety, the tank's weapons are now aimed directly at the tomb of Izdal, and Paul is thus able to negotiate from a position of strength. Zzaal had given his word that the Doctor would not be harmed, but honour counts for nothing if one is defeated. It appears that the Ice Warriors will have no choice but to destroy their enemy -- and his hostages.

The Doctor tries to convince Paul to give up peacefully, but he refuses to do so now that he's so close to victory. At least they'll have a fine view of the sunrise while they wait for the Ice Warriors to contact them. Paul admits to the Doctor that his father expected to find aliens here, which is why he financed the expedition to the anomaly -- and insisted that Tanya accompany them. To her horror, Paul reveals that eighteen years ago, the first experimental probes brought back organic material, with enough DNA for the corporation to begin their cloning experiments. Tanya always thought that she was an orphan -- but it's amazing just how much instinct she has inherited from her real family...

As the stunned Tanya tries to come to terms with this revelation, Zzaal contacts Paul, who offers to give up the Doctor as a hostage -- if one of the Ice Warriors agrees to take his place. Once Paul gets back to the command module, he will allow the Warrior to return. Although Zzaal is aware that Paul cannot be trusted, honour demands that he accept Paul's offer at face value, and he thus offers himself as a hostage, giving Paul his word that his Warriors will do nothing to endanger his life. Paul agrees triumphantly, and Zzaal departs after ensuring that Sstast fully understands the terms of the agreement. Which he does; to the letter. Peri angrily reminds Forbes that they could still warn the people in the command module about Paul's actions if only the communications on the Argosy were active, but although Forbes admits that he deliberately cut them off, he claims that the Brookings Report left him no option.

Tanya questions why NASA never revealed the presence of alien artefacts on Mars, and Paul and the Doctor cite the Brookings Report. When NASA was founded in 1958, the Brookings Institute made the recommendation that all of their findings be made public with a single exception -- the discovery of alien artefacts. This was considered unlikely, but still possible, and history provided numerous examples of civilisations which collapsed from culture shock after coming into contact with more advanced societies. This is why Forbes cut off their link to Earth when he realised that the anomaly was in fact an alien artefact. Zzaal arrives, and Paul orders the Doctor and Tanya out to join him, claiming that this day marks the dawn of a new technological order. The Doctor is sure that Zzaal is planning something, but isn't sure what; the daylight will not kill him, as the atmosphere is too thin to retain heat. Still, the Doctor begs Zaal to reconsider; but Zzaal knows that Paul cannot be trusted and knows that he has no other choice. He calls back to Sstast one last time to ensure that Sstast will not fire upon them while there is a chance he might harm his commander, and then signs off, telling Sstast that it has been an honour to serve with him.

As Paul leads his captives out onto the plain, Zzaal makes one last request -- he wishes to see the sun rise on his home world one last time. Paul sees nothing amiss, and allows Zzaal to watch as sunlight creeps across the plain -- beautiful, and, as the Doctor is coming to suspect, deadly. Long ago Izdal faced the Red Dawn and died, proving that his people had no choice but to evacuate their home, and now the sunlight falls across Zzaal -- who collapses, dying. The Doctor finally realises that it's not the temperature that is killing him, but the ultraviolet radiation; the atmosphere is too thin to retain heat, or to block out the sun's harmful rays. Zzaal, the only one of the party without a protective suit, is dying of sunburn. Knowing that the Doctor and Tanya have acted with honour, Zzaal urges them to flee, and then dies. As Paul stands stunned, realising that he has lost everything, the Doctor and Tanya make a break for it. Sstast then opens fire, despite Peri's and Forbes' protests, but the Doctor and Tanya are able to reach cover before the Warriors' sonic torpedo blows a new crater right where Paul had been standing.

The Doctor and Tanya return to the tomb, where Sstast tells them that he intends to contact his people and tell them that humanity has a lot to learn -- but that there is still hope for them. Tanya, feeling betrayed by her uncle, intends to remain on Mars to act as Earth's first ambassador to the Ice Warriors. Something good has to come of this; they must ensure that Zzaal did not sacrifice himself in vain. As Sstast prepares to take Forbes to their ship, to return to Ares One and make his report to NASA, the Doctor and Peri slip away quietly, intending to return to the TARDIS and set off for a new destination... wherever that may be.