October 1842 : archaeologists Horace Stockwood and Alexander Richards travel to Rapa Nui, also known as Easter Island. There, they befriend the natives, and when the son of their friend Tortorro falls ill, Stockwood helps to cure him. He then takes advantage of this act to convince the reluctant Tortorro to take him to the sacred Cave of the Sun's Inclination. The villagers find them there, and Stockwood panics and flees, taking the sacred rongo-rongo stick and abandoning his friends to the villagers. He hides in the tunnels which the natives use to hide from slavers, and emerges at night, to see a ceremony in which Tortorro apparently dies from nothing more than ostracism from the community. As Richards cries to him for help, Stockwood takes to his heels and flees back to his ship, pursued by the villagers. Panic-stricken and half-dead, he returns to England without Richards, but with the conviction that at the end, the moai, the great stone heads, walked across the island in pursuit of him...

August 1872 : Stockwood's only friend now is Dr James Royston; for the past thirty years he has been the laughingstock of the scientific community, and he is now almost completely bankrupt. He places an advertisement in the Times, seeking funding for a return expedition to Rapa Nui, and this catches the Doctor's attention. After hearing Stockwood's story, the Doctor agrees to fund the expedition, and converts gemstones from distant planets to ready cash for his purposes. Before leaving, he catches Stockwood's underpaid butler, Fennell, trying to rob the house, and dismisses him. In Portsmouth, the Doctor purchases the Tweed, but while he is thus occupied the TARDIS is accidentally loaded aboard a ship bound for India. The Doctor is then attacked and taken prisoner by a dockworker.

Leela becomes suspicious of Royston and determines to keep an eye on him, but Royston is just as suspicious of her; he is worried about Stockwood's sanity, and doesn't believe that the Doctor and Leela truly have his best interests at heart. He offers to join the expedition as a medical officer, despite Leela's objections. That night, Fennell breaks into Stockwood's home, and when Royston is forced to shoot him, Leela is convinced that he did so to prevent Fennell from being questioned about his accomplices. Stockwood decides to hide the body in order to avoid involving the police, which would delay his expedition. Royston's suspicions about the Doctor seem justified when they arrive in Portsmouth and find no sign of him, but Leela, while searching for the Doctor, is also attacked and kidnapped by the dockworker.

With only hours to go before the Tweed departs, Royston suggests leaving the Doctor and Leela behind, but Stockwood -- although finding it difficult to explain his instinctive trust of Leela -- refuses to abandon his friends again. Royston reluctantly accompanies him into the city to search for the missing Doctor and Leela, but they are also attacked and knocked out by the dockworker. Along with the Doctor and Leela, they awaken tied to the pier as the tide comes in. Leela manages to free herself and the others, and the Doctor sends Royston and Stockwood back to the ship while he and Leela try to find out why the dockworker tried to kill them. When they find him, he refuses to answer their questions, and instead tries to shoot them. They flee back to the Tweed, while the dockworker, pursued by police, is shot at and dives into the water just as the ship departs. The Doctor and Leela pull themselves on board -- only to find that Captain Stuart has accepted payment from the enemy who has been trying to stop their expedition; Alex Richard's sister Jennifer, who has hated Stockwood with a passion ever since he abandoned her brother to his death on Rapa Nui.

The Doctor convinces Richards to wait until they've reached Rapa Nui to take her revenge -- and convinces Leela not to kill her before then. Leela is still convinced that Royston intends to betray them, especially when she sees him privately offering money to Richards. Richards and Royston emerge from a locked cabin carrying soiled bandages, and Leela determines to find out who's inside. A cyclone blows the Tweed off course into the south seas and destroys their supplies of fresh water, and the crew must dock with a passing iceberg to replenish their supplies. Leela takes advantage of their distraction to break into the locked cabin, where she finds the dockworker, Stump, alive and delirious. Stump flees onto the iceberg, pursued by Leela, but as the iceberg begins to break up she retreats to the Tweed, leaving him to die.

Royston explains that Stump, although shot by the police, managed to catch hold of a rope hanging from the Tweed and pull himself aboard as it left Portsmouth. Royston tried to save his life because that's what doctors do; besides, by offering to pay off Richards and save Stump's life, he hoped to convince her to let Stockwood go without killing him. The Tweed enters turbulent waters where a whale and a giant squid are battling to the death, and Leela and Royston are both swept overboard. As the Tweed pulls ever further away, Leela is forced to kill the squid herself and to tie herself and Royston to the whale in order to survive. The whale is too seriously wounded to dive beneath the surface, and eventually dies, just as another storm approaches -- this time with a waterspout. Leela and Royston must climb inside the whale's mouth in order to ride out the typhoon...

The Tweed reaches Rapa Nui in December, although there appear to be no natives present to greet them. Stockwood is torn with guilt over abandoning Royston and Leela, but it's no less than Richards had expected of him; she lives now only to see him torn with madness over the grave of her brother. The Doctor, meanwhile, studies the moai and finds that their mass is fluctuating, which means that they are absorbing and transmitting energy somehow; but before he can investigate further, the Tweed is attacked by a fleet of Peruvian ships, and he and Stockwood realize too late why they have seen no natives. The Doctor finds a group of Peruvian slavers herding the natives together and tries to intervene, but the slavers shoot him in the chest. Stockwood flees into the tunnels, where Richards and the ship's boy Jack Devitt are hiding along with the natives. The others from the Tweed are prisoners of the Peruvian captain DaBraisse, as is the recovering Doctor.

Leela and Royston, having survived their ordeals, are rescued by Polynesian natives and taken to Rapa Nui. There, Leela whips up the natives' fighting spirit and prepares to lead them in an attack on the Tweed, intending to rescue Captain Stuart. But before they go, one of the islanders finally recognizes Stockwood, and brings forth his punishment -- the mad and emaciated Alex Richards, who has been kept alive in the caves for the past thirty years so the islanders may slit his throat before Stockwood's eyes. Leela then leads the islanders to the harbour while Stockwood and Jennifer Richards remain in the caves in shock. Having rescued Stuart from the Tweed, Leela then attacks DaBraisse's ship, where DaBraisse is forcing the Doctor to walk the plank. Stuart captures a Peruvian cannon and fires on DaBraisse's ship, and the other Peruvians are forced to retreat. DaBraisse, having survived the attack, retreats with them -- but not before mortally wounding Royston, who had just saved Leela's life. Leela realizes she was wrong to mistrust him.

Leela and the Doctor take the dying Royston back to the island, where Leela stops Jennifer from killing Stockwood and the Doctor determines that there's nothing he can do to save Royston. But the islanders have no quarrel with Royston, and the old woman who killed Alex Richards tells the Doctor to take Royston to the Cave of the Sun's Inclination, where the god will heal him. In the Cave, the Doctor finds the largest of all the moai, and realizes that it's a silicon-based, voice-activated alien computer. Richards still has the rongo-rongo, but Stockwood has kept a rubbing of it, and the Doctor is able to use it to activate the moai and send Royston, Stockwood, and Leela through a matter transport beam. The rubbing is incomplete, however, and the Doctor requires the rongo-rongo to bring them back; but Richards is now obsessed with the thought of Stockwood's death, and when DaBraisse returns to the island, she tries to make a deal with him to kill the Doctor and Stockwood. DaBraisse simply orders his men to kill her and attacks the Doctor, who wins the resulting swordfight. DaBraisse falls over a cliff to his death, and the islanders drive off the leaderless Peruvians while the Doctor carries the dying Richards and the rongo-rongo to the cave.

Stockwood, Leela and Royston find themselves in a vast metal city, and find that Royston's wounds have been healed by his trip through the transporter. Stockwood and Leela leave him to recover while they explore, and determine that the city is larger than the distance between London and Rapa Nui -- and is completely deserted. Royston recovers and stumbles through a nearby moai into yet another world, and Stockwood and Leela track him through a system of moai which leads them from world to world -- all of which appear to be deserted. They eventually catch up with Royston in the midst of a vast library, where they learn that the alien species which built this empire was devastated by war. Royston is overwhelmed with emotion at the evidence of deaths beyond counting.

The Doctor arrives with the recovering Jennifer, but despite the wonders she is being exposed to, Stockwood's death is still her only priority. The Doctor manages to activate telepathic connections in the library, and the truth is finally revealed. The aliens were all but wiped out during a war, and used the moai to scatter their DNA in retrovirus form throughout the galaxy, intending to hide from their enemies within the bodies of other life forms and then return to repopulate their planet once the danger was past. But the plan went wrong when the isolated Polynesians on Earth, exposed to visiting Europeans, became infected with some disease to which they had no immunity -- possibly the same disease which affected Tortorro's son -- and passed it on to the alien species when they began travelling through the moai. Thus the alien empire was wiped out for a second time. The Doctor, however, realizes that Leela, a descendant of space travellers from Earth's future, is immune to virtually everything currently in existence -- and that he can therefore use her blood to inoculate the islanders and allow them to repopulate the alien empire.

Richards stabs Stockwood and kills herself, and then Leela notices that the planet's sun is changing. The aliens, fearful of invasion after suffering from a devastating war, set up a doomsday device to turn their sun supernova if any species which did not contain their DNA structure set foot on their planet. The Doctor and his friends retrace their steps through the moai, back to Rapa Nui, healing Stockwood and saving the alien world. Stockwood then decides to remain on Rapa Nui to atone for his misdeeds by protecting the villagers against other slavers and "men of knowledge" such as himself. The Doctor and Leela set off for India to search for the TARDIS, and Royston returns to London on the Tweed. Over the following decades, the islanders use the moai to travel to the distant homeworld and reclaim their alien inheritance. Finally, in December 1902, as the last party of islanders departs from Rapa Nui, Stockwood accompanies them to see the last sight of his life, the most wondrous sight of all; a world reborn.