In the TARDIS, the four travellers are huddling around the Time-Space Visualiser, a television-like souvenir from their recent adventure at the Space Museum, which can pick up on any past event in the whole of time and space. They each choose an event to witness: Ian picks Abraham Lincoln giving his Gettysburg Address; Barbara elects to look into Elizabeth I's court, and sees the genesis of two Shakespeare plays (The Merry Wives of Windsor and Hamlet); and Vicki sees the Beatles performing "Ticket to Ride", but is surprised that they should play "classical music"!
The TARDIS then lands, and the Doctor confirms that the conditions are hospitable. Ian and Vicki leave to explore the desert wilderness, the former entrusted with the "TARDIS magnet" in case they should get lost. Vicki investigates some formations which appear similar to seaweed, which Ian knows is impossible. They then find a trail of what appears to be blood in the sand, which Vicki runs off to follow. As they move off, they do not notice a tentacle rise up from the sand where they were standing.
Meanwhile, the Doctor and Barbara are sunbathing. Barbara is distracted by the sound of the Visualiser, which has not been shut off. She sees on it a "broadcast" of the Daleks preparing to give a report. The Doctor enters and hears, to his horror, the Daleks' plan to follow "the enemy time machine" (the TARDIS) to the Sagarro Desert on the planet Aridius. The Dalek Seventh Incursion Squad will take the TARDIS, find the Doctor and his companions, and exterminate them. The Doctor and Barbara watch the Incursion Squad embark and dematerialise. The Doctor immediately realises that these events happened in the past — the Daleks may already be here. They must find Ian and Vicki and leave immediately.
Tiring from their walk, Ian and Vicki take a rest as the "blood" trail ends. In the sand, they find a large metal ring. At first, Vicki is reluctant to disturb it for fear of what might happen (due in no small part to a similar ring from her childhood). However, they decide they should pull it loose, and Ian duly does just that. At first, nothing happens and they prepare to leave, but then an ancient trap door creaks open in the sand. Vicki and Ian go inside the newly-opened cavern to have a look. Once they are inside the trap door closes behind them: they are trapped — and another tentacle looms out of the darkness. It seems the creatures are everywhere.
Meanwhile, the Doctor and Barbara have had no luck finding their friends, night has fallen and the wind has begun to pick up, covering all tracks including their own. They decide to return to the TARDIS, not entirely certain of the direction, as the TARDIS may have been covered by the sand. A sandstorm breaks out which lasts all night. When they awake they see a Dalek, buried by the sandstorm, emerging from the sand. Two other Daleks soon arrive as well. They cannot find the time travellers, but they do locate the TARDIS under the sand and begin to have it dug out by a group of native Aridians, whom they have enslaved. The slave force is exterminated when they are of no further value.
The Doctor and Barbara are saved by other amphibious humanoid Aridians, who explain that Aridius was not always a desert, but that the suns have got nearer the planet and destroyed the seas. Only themselves and the hideous Mire Beasts are left, and the Mire Beasts can only be contained by destroying sections of the Aridian city that have become over-run. The Daleks soon contact the Aridians in the underground city and tell them they will leave Aridius if the Doctor and his party are handed over, and the elders agree to this arrangement. The Aridians also find Vicki and Ian, who were injured when a wall collapsed in an explosion used to kill the Mire Beasts that were threatening them. The Mire Beasts soon reappear, killing the Aridian Malsan who was holding the party prisoner in preparation for the handover. The Doctor and his friends flee in the confusion and manage to evade a Dalek scout and get back to the TARDIS.
There now follows a chase through time and space, with the Dalek vessel determined to track down and exterminate the Doctor and his friends. The Daleks are but fifteen minutes behind and the gap is closing. The first stop is the top of the Empire State Building in New York, where a young man from Alabama, Morton Dill, tells them it is 1966. Fortunately for him, neither the TARDIS nor the Dalek time vessel stays long and his life is not imperilled. The Doctor next reaches the Atlantic Ocean and boards a sailing ship. The crew ventures outside and are mistaken for stowaways. They sneak away in the TARDIS as the crew searches the ship for them. Soon the Daleks arrive and the frightened crew abandons ship, all jumping overboard (along with one Dalek in pursuit of them, demanding to know the whereabouts of the TARDIS crew). As the Dalek time vessel departs, it is revealed the ship is the legendary Mary Celeste.
The next point of landing is a mysterious old house where both Dracula and Frankenstein's monster have come alive. These terrors stalk the building but also attack the Incursion Squad when they arrive. In the confusion to depart, the Doctor, Ian and Barbara leave Vicki behind, never realising they have simply been visiting a futuristic theme attraction called the Festival of Ghana, in 1996. The Daleks are repelled back into their vessel by the monsters (who are in fact robots), and Vicki stows away aboard the Dalek ship. She travels in it to the jungle world of Mechanus, where the Doctor's TARDIS has already landed.
The Doctor, Ian and Barbara are very sad about Vicki's possible fate at the hands of the Daleks, and blame themselves. They decide their only chance to rescue her is to try and take control of the Daleks' own time vessel. On the Dalek ship, Vicki witnesses the Daleks' Replicator machine in action: an android replica of the Doctor is produced and is programmed to kill the original Doctor and his companions. When the Dalek ship arrives on Mechanus, the robot killer is dispatched. The jungle is also hostile, with large fungoid plants which attack humans and only retreat when exposed to light. The time travellers now split up and Barbara stays behind to protect a machine the Doctor has built to defend them from the Daleks. She encounters the robot Doctor, while Ian and the Doctor are reunited with Vicki, who is hiding in the jungle. After a while the four travellers are reunited and the real Doctor unmasks the robot counterpart, disabling it with his stick.
The Daleks have fallen victim to the planet's fungoid creatures as well and call off their search until the morning, letting the Doctor and his party sleep freely in a nearby cave. In the morning, the Doctor notices that there is vast metal city over the jungle, and they all decide to venture into the structure. Within moments, a robot Mechonoid arrives and invites them into the city. It is obviously armed, but says it means them no harm, so they do as they are bidden and enter the Mechonoid city. Other Mechonoids are there too, as is a dishevelled man named Steven Taylor. He is an astronaut from Earth who crash-landed on the planet two years earlier and has been kept as a prisoner by the Mechonoids since then. The city Mechonoids are colonising robots built to make the city for human colonisers that never arrived, and so their current guests will be kept in the city permanently — Steven has not been permitted to leave.
The Daleks now attack the city, so it is time for action. The Doctor and his party and Steven manage to escape from the city down some cables, while the Mechonoids and Daleks become involved in a pitched battle, as shown in the picture above, which devastates both sides as well as the building. The four companions flee to safety but are separated from Steven, whom they presume to have been killed.
For Ian and Barbara it is decision time. The navigable time machine gives them a chance to get back to modern-day Earth. They find the deserted Dalek time machine and persuade the Doctor to show Ian how to operate it. After a tearful farewell, Ian and Barbara return to their own planet at last — and almost to their own time, being two years out in London of 1965. The machine is destroyed using the auto-destruct mechanism once Barbara and Ian are out of it.
The Doctor and Vicki oversee their farewell on the Time/Space Visualiser, glad they made it, but the Doctor is very sad at the loss.