Chief Co-ordinator Whitten has orders to evacuate at least 2000 people from a certain Australian shantytown, whether they want to go or not. He has tried not to resort to force, but time is running out, and as the crowd begins to chant, Whitten sends his men in with tear gas canister. But as Whitten addresses the crowd, insisting that this is for their own good, the earth itself begins to quake beneath their feet. Whitten orders his men to fall back, but it’s too late...

The TARDIS materialises in a city floating through the depths of space; it’s as if the entire island of Manhattan has been uprooted from the Earth. The atmosphere is breathable, presumably maintained behind a force field, but the city is weirdly deserted. As the Doctor, Ace and Hex explore their surroundings, they find a set of standing stones in the middle of the street, and the Doctor recognises a lizard basking atop one of the stones as a moloch, or thorny devil; it’s an Australian reptile named after a demon in Paradise Lost. The stones themselves seem to be made of a soft baked clay, and Ace can make out screaming faces crudely etched into their surfaces. Hex is unnerved by his surroundings, and is then awed to see an alien spaceship landing nearby; it seems that the Doctor and his companions are not the only visitors to this city.

The spaceship belongs to the Galyari, who have found the city and intend to investigate the possibility of trade with its inhabitants. Commander Korshal and his troops accompany Trade Director Vresha out onto the surface of the asteroid, but they are unable to detect any life signs -- or any indication of the powerful forces that must be holding in the atmosphere, maintaining the city’s artificial gravity and propelling it through space. Korshal concludes that the city is dead, and anticipates salvaging its advanced technology -- but a panic-stricken woman named Leanne Toomey then rushes out of the shadows, desperate to get away from the city. Vresha and Korshal try to calm her, but the hysterical Toomey insists that there’s nobody here to trade with, and begs the visitors to take her away before it’s too late.

Hex spots more standing stones in the street, these more like crude effigies of stone cars. The Doctor then spots something even stranger at the end of the street: it seems that this city has been built around the famous Australian landmark of Ayers Rock, or Uluru. The Doctor begins to form some theories about the statues, but is unwilling to share them until he’s sure he’s right; however, he does warn Ace and Hex that they could legitimately be regarded as trespassers here. Instead of continuing on towards the alien ship, the Doctor decides to investigate Uluru first; he too has noticed that the gravity and atmosphere is all wrong for an asteroid of this size, and suspects that he might find an explanation there. Ace and Hex can’t shake off the feeling of being watched, and the Doctor explains that he’s looking for more recent cave paintings that might reflect this city’s culture; he suspects that they’re walking through someone else’s dream, a different truth that doesn’t match their own preconceptions. His musings are interrupted by the arrival of a man and a woman in an electric car; these are Dream Commandos Mulyan and Wahn, who fire warning shots over the newcomers’ heads and order them into the car.

Vresha and Korshal attempt to question the panic-stricken Toomey, but she seems unsure what’s happened to the city. As a mining engineer, she didn’t have clearance to go near the asteroid’s propulsion systems -- if indeed there are any. The Galyari hear the warning shots fired by Wahn and Mulyan, and though Toomey claims that there may still be Dream Commandos active in the city -- special forces trained to hold back the Dreaming -- she insists that fighting the Dreaming is a lost cause and begs the Galyari to take her away. Korshal and Vresha decide to seek out these Dream Commandos, but Toomey is convinced that they’re all going to die. Shapes begin to move in the shadows and advance on the Galyari, and Toomey flees, leaving them to their fate. The Galyari retreat, firing at their shadowy pursuers, but lose track of Toomey in the shadows. The Galyari have their own legendary nightmares, but Korshal is confident that his enemies here are real and solid, not myths and dreams as Toomey seemed to believe. He thus decides to track down the Dream Commandos and offer military assistance in exchange for trade with the Galyari Clutch.

The earth has reclaimed the Doctor, and the Dream Commandos warn Hex that the threat has not passed. Hex is reluctantly forced to abandon the Doctor and carry Ace to safety, but as he and the Commandos retreat, the bunyips return and close in on them. Wahn drives them back with her bull-roarer, and the Galyari then show up and add their firepower. The humans and Galyari take shelter in an abandoned building, and while the Galyari troops stand guard outside, Vresha offers Hex a basic medical kit so he can tend to Ace’s injuries. Wahn thanks the Galyari for their help, comparing their multi-coloured armour to the skin of Galaru, the Rainbow Serpent; however, she and Mulyan do not believe that the Galyari can be of any further assistance, as the aliens seem convinced that they’re facing an ordinary, external threat and that the humans on this colony have simply mythologised what they do not understand. Ace then awakens, and Hex brings her up to speed, assuring her that the aliens (his first real, live aliens) are on their side. However, he’s forced to admit that something has happened to the Doctor...

Toomey and the Doctor are in a strange void, surrounded by screaming voices. The Doctor urges Toomey to concentrate on her own identity and focus on maintaining her sense of individuality. She’s terrified, but he’s fascinated -- and when he takes a metaphorical look around, he senses what appears to be a bridge across the abyss. Toomey begs the Doctor not to abandon her, but she’s unable to move, and he’s determined to help not just her but everyone trapped here. He crosses the bridge into the past, leaving the panic-stricken Toomey behind.

Korshal becomes wary when Ace and Hex claim to travel with a man called the Doctor, but concedes that he is unlikely to be the Sandman of his people’s legends. Ace is certain that the Doctor can resist whatever’s thrown at him, and Wahn and Mulyan concede that it has been possible in the past to draw souls back out of the Dreaming; however, it has become stronger with each soul it’s taken into itself, and now recovering the lost is virtually impossible. Certain loud sounds, like gunfire or the throbbing hum of the bull-roarers, can disrupt the Dreaming for a time, but the Commandos claim that sonics are just half the weapon; the sound must speak with the spirit of the warrior to be effective. Korshal concludes that they’re talking about psionic powers, and is revolted by the thought; for cultural reasons, the Galyari regard telepathy as a freakish aberration. Mulyan insists that the power is more spiritual than that, and doesn’t care what the Galyari choose to believe; as far as he’s concerned, none of the others should be here, but the electronic beacons warning visitors away have failed as the Dreaming takes hold of the city.

Back in the past, Chief Co-ordinator Whitten and his driver are circling the shantytown that has sprung up around Uluru when they encounter the Doctor, who seems to have walked out of the desert. Whitten places him under arrest, assuming that he’s another nutcase here to soak up the mystical rhythms of Uluru; however, he soon realises that the Doctor genuinely didn’t know that the shantytown was here. Whitten explains that he’s in charge of evacuating at least 2,000 Aborigines onto the Phoenix lifeships before the end of the world; however, there isn’t enough room for everybody on board, and it seems that these people have fallen under the spell of a guru named Baiame who has offered them some mystical alternative to extinction. Whitten has organised a methodical evacuation plan, and he’s determined to meet his quota; he has nothing but contempt for Baiame, as he’s convinced that the guru’s empty promises will keep his believers trapped on the Earth until they’re scorched away to nothing. The Doctor decides to try talking with Baiame, and Whitten takes offence at the Doctor’s tone. He has not yet resorted to force, and many of his men don’t have spaces on the lifeships themselves; they have chosen to stay here and help these people rather than spend time with their families during the last days of Earth, and their sacrifice is going unappreciated. Nevertheless, Whitten agrees to let the Doctor try to talk some sense into Baiame, and the Doctor asks him not to do anything rash in the meantime.

In the fallen city, Korshal gives up trying to get any sense out of the Dream Commandos, and when they turn down his offer to evacuate them, he storms out of the building, leaving them to their fate. However, Vresha catches up to him outside and reminds him that Leanne Toomey claimed to be a mining engineer; the minerals with which to build the city must have been mined out of the heart of this asteroid, which would be the most likely place for the city’s founders to have placed the propulsion systems and gravity generators. It is still worth the Galyari’s time to stay here and investigate the technology holding this place together. Korshal and Vresha thus return to the building and suggest that it’s possible for other survivors to be located in the mines. Mulyan agrees to lead them to a nearby access tunnel, and Ace accompanies the Galyari back to their ship for power generators and sonic weapons. In the meantime, Wahn leads Hex back to the Doctor’s stone, hoping to wake him from the Dreaming.

Baiame knows the history of this land, and he knows of the wrongs that were committed; his own people now seek a fresh start, unencumbered by the pain of the past, and Whitten and his men are not invited. But the Doctor insists that if Baiame abandons Whitten’s troops to their deaths, then his people’s future will have been founded on death, and the dream will be corrupted and weakened from its very beginnings. Baiame accepts the Doctor’s argument and agrees to extend his influence a bit further -- and thus, when Uluru tears itself free of the earth and drifts off into the stars, Whitten and his men are taken along with it. The Doctor travels to the edge of the new land to rescue Whitten from his Jeep, which is teetering on the edge and about to fall into the abyss. Whitten is almost unable to comprehend what’s happened, but the Doctor advises him to accept his new fate as part of an ethnic minority; at least he and his men are still alive. The Doctor wishes Whitten goodbye and good luck, and returns to speak with Baiame, leaving the stunned Whitten to pull himself together and try to organise his men to deal with their new life.

In the fallen city, Wahn and Hex find that the Jeep has been also turned to stone, reclaimed by the earth. They are then surrounded by maletji, the dogs that carry tribal law out of the Dreamtime. Hex is forced to use Wahn’s rifle to drive them back, an experience that reminds him unhappily of his father’s failed attempts to bond with him through hunting trips. Wahn drives the law dogs back to the Dreamtime with her bull-roarer, but warns Hex that they don’t scare easily and urges him to communicate with his friend before they return. On Wahn’s instructions, Hex lays his hands on the Doctor’s stone and tries to concentrate on good memories of the Doctor while the throbbing hum of the bull-roarer passes through his body and into the stone. His first attempt fails, as he’s trying too hard, but he relaxes and tries again -- and this time, thunder peals overhead and the buildings of the city begin to melt into the earth. In trying to wake the Doctor, Hex appears to have disturbed something far worse.

The Galyari have fetched sonic engineering tools from their ship, but while the weapons are capable of boring a hole through the asteroid, Mulyan remains unconvinced that mere sound without spirit will be enough to drive back the Dreaming. Korshal, for his part, remains convinced that the people of the city have mythologised the effects of malfunctioning technology; however, he does take note when Mulyan explains that the Dream Commandos were trained by Baiame, the all-father who raised this city to the stars and who now resides in the Dreamtime. As Ace, Mulyan and the Galyari descend into the mines, something leaps onto the roof of the lift and begins to claw its way inside. The Galyari are unable to use their sonic weapons in the confined space, and Ace thus suggests cutting the power and letting the lift fall; the emergency brakes are mechanical and should prevent the lift from crashing, but it will reach its destination more quickly. Vresha does as Ace suggests, and the lift plummets to the bottom of the shaft. There, Korshal forces open the doors, but when he and his allies emerge, there is no sign of their attacker.

Back in the past, the Doctor thanks Baiame for showing mercy and assures him that Whitten’s people will prove an asset. Baiame agrees to guide the Doctor back through the Dreamtime to his friends. The Doctor understands that Baiame is older than he appears; he wandered the earth when it was still young and found his way to the heart of Uluru, where he became attuned to the Dreamtime and the spirit of the land. The Doctor joins Baiame in the Dreaming to sleep away the centuries, but as history passes around him, he senses it going wrong. The heart of Uluru is more than just rock; myth and legend have been woven through the fabric of creation like a third strand of DNA, binding the people and their culture to their land. When Uluru reached its new world, the Dreaming was supposed to spread out and reshape that world in the people’s image, like a kind of mythological terraforming -- but the Doctor now realises that the process has been triggered prematurely, and it’s reducing all life on the asteroid back to a raw, primordial state from which to begin again. To his horror, the Doctor realises that he’s responsible.

In the fallen city of the future, Wahn and Hex see the last of the streetlights go out. The spirits of death are coming out of the Dreaming, and Hex and Wahn flee back to the lifts to join forces with their friends. But when they arrive, they see that the two Galyari left on guard have turned to stone -- and then they hear footsteps, as something woken from the Dreaming approaches them...

Ace surfaces with one of the Galyari’s sonic blasters, and when she and Korshal concentrate their fire, the image of the Doctor is dispersed. In the confusion, however, Vresha has been taken by the Dreamtime and turned to stone. Korshal is forced to flee to higher ground with Ace and Mulyan as the water rises, but, infuriated by Vresha’s loss, he vows to put an end to this nightmare. Mulyan protests when it becomes clear that Korshal intends to break into the sacred space at the heart of Uluru, but Korshal is convinced that a machine or madman sits at the heart of this horror, and he vows to destroy it and reclaim Vresha. The waters from the reservoir rise and flood the tunnel, as, in Mulyan’s terms, the rainbow serpent tries to protect the sacred rock from those who would attack it. Despite Mulyan’s objections, Ace and Korshal use their sonic blasters to bring down the roof and block the tunnel, and they retreat as the waters hammer at the makeshift dam.

The Doctor now understands what has happened to Uluru City, and with Baiame’s guidance, he intends to return and put things right; however, Baiame warns the Doctor that the spirit of death has taken his form to walk in the city. The Doctor leaves the Dreamtime, and soon afterwards, Vresha finds herself in the void. She accuses Baiame of attacking those who came peacefully in search of trade, but he denies responsibility; it is the Dreamtime that identified them as intruders and sought to expel them. However, now Korshal believes that Baiame is the root of this evil and intends to destroy him -- and Baiame realises that Korshal, driven by his loyalty to his troops and his feelings for Vresha, is too determined for the Dreaming to hold back. Desperate, Baiame calls on the Doctor for help, knowing that they are all doomed if Korshal succeeds.

Hex and Wahn are relieved when the footsteps they are hearing turn out to be the Doctor’s. The city begins to break up around them as the earth reclaims its raw materials; building sink into the ground and hot geysers erupt from the surface. The Doctor reveals that this is happening because he convinced Baiame to accept Whitten’s people into his new society; the people of Uluru City subsequently came to accept Western ideas into their culture, and lost sight of their own heritage, changing their old traditions to suit their new ideas. And since the power of the Dreaming is rooted in ancient belief, those powers began to weaken when the belief began to wane -- and the Dreaming took action to save itself by drawing everything back to the beginning. The Doctor still believes that saving Whitten and his people was the right thing to do, but now he must deal with the unexpected consequences. He then hears Baiame calling for help, and rushes to the Galyari ship to contact Korshal. Korshal believes that Uluru City is founded on advanced technology that he doesn’t fully understand, but in truth it’s held together by Baiame’s willpower, focussing the dreams of an entire culture -- and if Korshal kills Baiame, the city will come apart completely, dooming them all.

Down in the mines, Korshal, Ace and Mulyan reach a dead end, which Mulyan recognises as the heart of Uluru. Korshal begins to cut through the sacred rock, and when Mulyan tries to intervene, Korshal knocks him unconscious. Ace protests, but must concede that the water pressure behind them is continuing to build and that they have little choice but to keep going forward. As they dig, the Doctor contacts them and tries to convince them to stop, but Korshal refuses to listen, convinced that this voice is another illusion generated by their enemy, like the image of the Doctor that confronted them at the reservoir. He and Ace thus break through into Uluru’s heart, where Ace is surprised to find that Baiame is just an old man who seems resigned to their arrival in his domain. However, Korshal remains convinced that this apparently harmless old man has used foul psionic trickery to attack them, and though Baiame tries to explain that he is not responsible, Korshal turns his sonic blaster on the old man.

Unable to get through to Korshal, the Doctor instead tries to communicate with the Dreaming. Fortunately, the Galyari are quite large, and there is enough room inside their ship’s communications suite for Wahn to swing her bull-roarer. The Doctor records the sound and manipulates it with the equipment in the suite, hoping to reproduce the sound of the bull-roarer and imbue it with something of his own spirit. As he works, the Galyari ship is surrounded by bunyips and maletji, and Hex and Wahn leave the safety of the communications suite to hold off their attackers and buy the Doctor time to work. As he works, Baiame calls on him for help, but the Doctor is too busy, and he advises Baiame to call on some of his other friends from the Dreaming.

Ace can’t stand by and watch Korshal kill a harmless old man, but when she tries to shoot the sonic weapon out Korshal’s hands, he knocks her aside. However, the delay gives Baiame time to summon a kookaburra, which flies out of the Dreaming and places itself between Baiame and Korshal. Birds are sacred to the Galyari, and even though Korshal believes that this must be an illusion, he can’t bring himself to fire at it. This gives the Doctor time to finish his work, and when he activates the external communications system, the sound of the bull-roarer echoes out of every communications unit and speaker in the city, blanketing it with sound. The creatures surrounding the ship fade back into the Dreaming, and the people of Uluru City wake, including Leanne Toomey -- and including Vresha and the Galyari troopers. Baiame assures Korshal that Vresha is now flee, and the kookaburra flies to the frustrated Galyari warrior to put his heart at peace.