A cybernetic alien woman fleeing from a space battle crashes her escape pod on the plains of Mesopotamia, where she meets Gilgamesh, king of Uruk. She tries to lure him into her clutches and seize control of his mind, but he is too wily for her and returns to Uruk safely to tell how he outwitted Ishtar, goddess of love and war. As the divine god-king of Uruk, he has the right to do whatever he pleases, and he is apparently oblivious to the resentment the city’s noblemen feel as he sleeps with whichever of their wives and daughters take his fancy. Two such noblemen, Ennatum and Gudea, convince him to investigate rumours of odd events in the city of Kish, but send word ahead to ensure that King Agga of Kish is prepared for his arrival. But by this time, the alien has seized control of Kish’s high priest Dumuzi and established herself in Kish’s temple. Agga hates and fears Ishtar for what she has done to his city, but he also fears what she might do if he acts against her, and thus agrees to all of her demands -- to the disgust of his daughter Ninani, who vows to rid her city of the evil goddess.

The Doctor accidentally erases Ace’s memories while using the TARDIS telepathic circuits to edit his increasingly cluttered memory. While fixing the problem, he triggers a recorded message from his fourth incarnation, a warning of something he learned while connected to the Matrix on Gallifrey -- an evil which the ancient Time Lords called Timewyrm. The details of his discovery are erased from his mind by the Matrix safeguards even as he speaks, however, and the Seventh Doctor thus has no idea why his past self left this warning. The TARDIS then alerts him and Ace to the presence of a temporal anomaly in ancient Mesopotamia, which could conceivably end all of human history. They materialise in the midst of a battle between Gilgamesh and his Neanderthal friend Enkidu, and the soldiers sent from Kish to ambush them; Ace uses nitro-nine to drive off the attackers, thus convincing Gilgamesh that she and the Doctor are gods. When the Doctor learns that Gilgamesh is on his way to investigate odd events in Kish, he decides to join the expedition, and as they approach the city he sees that the copper patterns on the walls are not tarnishing -- which should not be possible in this era.

Ninani orders her maid Puabi to summon a priestess from the Temple, and Puabi thus contacts her young niece En-Gula. Ninani explains that she wishes to destroy Ishtar, and although En-Gula is at first hesitant and awed to find herself in the company of a princess, she eventually tells Ninani all she knows about the horrors which have been visited upon the temple. Formerly friendly priests and priestesses have started to change or go missing, and it has been said that the bodies of those who have vanished have later been found with their brains removed from their bodies. One night, En-Gula entered the forbidden inner sanctum of the temple to observe Ishtar herself, and saw the goddess take on the form of a great silver snake-woman and place her hand on the forehead of an unlucky priestess. When En-Gula next saw the priestess, her entire demeanour had changed; it was as if she had become one of the walking dead. Having unburdened herself, En-Gula promises to help Ninani do whatever she can to destroy Ishtar before the goddess destroys their city.

While Ace tries to keep Gilgamesh occupied, the Doctor visits the temple of Ishtar to pick up the local gossip. There, he meets En-Gula, who directs him to Dumuzi -- but Dumuzi seems oddly unfazed by the Doctor’s deliberately odd behaviour, and when the Doctor requests an audience with Ishtar, Dumuzi has him drugged and left to await her Touch. Meanwhile, Ace, Enkidu and Gilgamesh wait for the Doctor at a local inn, where Ace soon determines that the god-king is not nearly as divine as he considers himself to be. While trying to ignore his loutish behaviour, she strikes up a conversation with the songsmith Avram, who confides that Kish has become an unfriendly place since Ishtar came to dwell in the temple. Concerned for the Doctor, and fed up with Gilgamesh, Ace sets off for the temple with Avram; there, they also meet En-Gula, who senses that the strangers can help her and takes them to the chamber where the Doctor is being held. He appears to be unconscious, but in fact he is using his respiratory bypass system to keep his captors off guard while he awaits his audience with Ishtar. However, Dumuzi catches Ace and her new friends trying to rescue the Doctor, who has no choice but to flee with them while Ace uses nitro-nine to discourage pursuit. Meanwhile, Gilgamesh and Enkidu are recognised when the frustrated god-king picks a fight with another patron at the inn, and they too are forced to fight their way out of the city.

Ishtar is infuriated to learn that Gilgamesh has once again escaped her clutches, but becomes intrigued when she examines the remains of Ace’s explosives. The strangers are clearly not of this world or time, and could pose a threat to her plans. She therefore orders Agga to advance the schedule for the completion of the copper patterns on Kish’s walls. She is well aware that he hates and fears her, but she keeps him in line by threatening the life of his daughter -- and warns him that even if by some miracle he manages to kill her, at the moment of her death a cobalt bomb which she has linked to her brain-wave patterns will explode, destroying the entire Earth. Meanwhile, Ninani learns that En-Gula has fled with those responsible for the attack on Ishtar’s palace, and fears that her part in the conspiracy may be discovered.

The Doctor and Ace compare notes, listen to En-Gula’s story, and theorise that “Ishtar” is controlling her slaves with implanted radio receivers -- which would also explain the copper plating on the city walls. Once the designs are complete, Kish will become a gigantic radio transmitter, and the as-yet untapped oil and coal deposits beneath the sands of Mesopotamia will give Ishtar the power to spread her influence over the entire world. Gilgamesh tells the Doctor of his own encounter with Ishtar, and leads him to the place where he found the fallen goddess. The Doctor identifies her dwelling as a spaceship’s escape pod, and defuses a thermite bomb which had been left as a booby trap. Ace pockets the bomb while the Doctor isn’t looking. The pod has been stripped of all its technology, but Avram recognises a sigil on its walls, and claims to have seen a similar icon when he encountered the Zuqaqip, the scorpion men who dwell in the mountains of Mashu. The Zuqaqip allowed him to depart in peace with a talisman with which to remember their meeting, and when the Doctor examines the talisman, he realises that it is in fact a printed cirucit.

The Doctor and his allies return to Uruk, where the frustrated Ennatum has Gudea killed so he will not betray their part in the conspiracy against Gilgamesh. Gilgamesh himself demands a feast to celebrate his triumphant return, and while Ace is appalled by his openly lecherous and drunken behaviour, the Doctor tells her that any behaviour on the part of the god-king is deemed acceptable by the standards of this society. The Doctor then asks Avram to tell him about the Zuqaqip, and Avram obligingly sings of the god Utnapishtim’s war with the evil Ishtar. The vengeful goddess sent a flood to destroy the world, but Utnapishtim built an ark to save himself and his followers. Ace thinks it’s just another myth, but the Doctor reminds her that in the lowlands between the Tigris and Euphrates rivers, floods are indeed a regular and devastating occurrence which could seem like the end of the world. Avram is just applying his own cultural filters to the story which he has been told, and when Ace reads between the lines she realises that he is describing the flight of an alien space ark from a doomed world -- and that somewhere in the mountains of Mashu is an enemy of Ishtar’s, who may be able to help them defeat her.

The Doctor tells Ace to take Avram and Gilgamesh to find Utnapishtim. Gilgamesh still believes that the Doctor and Ace are gods, and thus he refrains from forcing himself upon Ace, but by the time they reach the mountains Ace is grateful that the trip is over -- and Gilgamesh, who has never been rejected before, is frustrated, angry and spoiling for a fight. The Zuqaqip prove to be robot guardians who refuse to let the visitors past until Ace shows them the thermite bomb from Ishtar’s escape pod, proof that another native of their planet is on Earth. The Zuqaqip allow Ace and her companions to pass by into a flooded caldera, where they meet a man named Urshanabi who refuses to take them to Utnapishtim until they explain their business to him. Gilgamesh boils over, beats him senseless and smashes up his boat -- and realises too late that as the caldera has been stocked with carnivorous fish, he’s just destroyed their only means of getting to Utnapishtim. Having worked out his anger, Gilgamesh acknowledges that he let his temper get the better of him, and contritely repairs the boat, using the broken mast as a punt to cross to the island in the centre of the caldera.

The island turns out to be the entrance to a vast, buried spaceship the size of a city. As Urshanabi takes the awed Avram and Gilgamesh for refreshments, Ace speaks with Utnapishtim -- who reveals that the city-ship is irreparably damaged, and that he and his people will soon have no choice but to wipe out the warlike inhabitants of Earth and make their new home here. Ace, however, reveals that she is from the future, and that there is no evidence in her time that Utnapishtim or his people ever existed. Shattered, Utnapishtim explains that his own homeworld, Anu, was destroyed by the brilliant but evil Qataka, who became obsessed with her fear of death and thus began killing people and harvesting their neurons to replace her own dying brain cells. She was captured, tried and executed, but Utnapishtim, who carried out the sentence, became convinced that she had somehow found a way to cheat death. He thus built this space ark and evacuated all who would listen to him -- just in time, for Qataka had in fact uploaded a copy of her mind into a cybernetic body at the moment of her death. She and her own followers fled from Anu, detonating a cobalt bomb which destroyed the planet behind them. Utnapishtim believed that he had destroyed her in their final battle over the Earth, but Ace reveals that she is now in Kish, and calling herself Ishtar. Ace promises that if Utnapishtim helps to defeat Qataka, then the Doctor will in turn help his people to survive. Utnapishtim therefore returns to work on a software virus which he hopes will shut down both Qataka’s cybernetic mind and body, if only he can somehow upload it into her...

The Doctor returns to Kish with Enkidu and En-Gula to enlist Ninani’s help, but although they manage to get into the palace, Agga catches them trying to contact his daughter. Fearing for her life and furious with her for conspiring with their enemies, Agga confines her to her rooms and sends the intruders to the dungeons. But Ninani will not stand quietly by while Ishtar destroys them all, and she thus knocks out her guard and releases the others. En-Gula leads her friends to the temple, where the Doctor gets into Ishtar’s inner sanctum, only to be captured by the snake goddess, along with his friends. Ishtar summons Agga to witness his daughter’s punishment; it is not enough for her to win unless her enemies also acknowledge their defeat. She kills Dumuzi as a casual demonstration of her power, and places a radio implant in Ninani’s brain, intending to inflict all manner of degradation upon her body as Agga watches helplessly. Having learned that the Doctor is one of the legendary Time Lords, she prepares to place an implant in his mind as well, to learn the secrets of time travel and immortality -- but before she can do so, Ace, Gilgamesh and Utnapishtim arrive in shuttles from the city-ship and attack Kish.

The attackers fight their way into Ishtar’s sanctum, but before Utnapishtim can upload the virus into her systems, Ishtar overpowers him and destroys the disc. Her guards capture the remaining attackers, and Ishtar forces the Doctor to watch as she puts an implant in Ace’s brain -- but the moment she does so, she collapses in agony. The disc was a decoy; Utnapishtim in fact imprinted the real virus upon his attackers’ mental patterns, and Ishtar has just infected herself. But Utnapishtim didn’t realise that at the moment of her death a cobalt bomb will destroy the Earth. The Doctor takes Ace back to the TARDIS in one of the city-ship’s shuttles, but he is insecure about his own technical expertise and thus uses the telepathic circuits to temporarily summon forth his third incarnation’s personality traits. He draws the implant out of Ace’s brain and connects it to the TARDIS telepathic circuits, convincing the cobalt bomb that Ishtar is still alive and giving him a chance to defuse it. But before the Doctor can switch off the implant, Ishtar fights off the effects of the virus and transmits her personality through the telepathic circuits and into the TARDIS itself. As the TARDIS attempts to fight the intruder, Ishtar threatens to use its life support controls to torture the Doctor until he tells her how to control the ship’s systems. He informs her that life support can only be accessed from the secondary console -- and when Ishtar transmits her mind into the secondary console to investigate, he isolates the room from the rest of the ship and ejects it and the other infected circuits from the TARDIS.

Satisfied that Ishtar has been destroyed, the Doctor strips her technology out of the temple in Kish and uses it to repair Utnapishtim’s city-ship. Utnapishtim and his people depart for a new life on an uninhabited world, and Agga and Gilgamesh make peace with each other. Ace is cheered by the happy ending until the Doctor tells her to look beyond the surface of things; Agga will now force Ninani to marry Gilgamesh against her will to cement their alliance, but soon Enkidu will die of a wasting disease and the grieving Gilgamesh will attack Kish anyway. Avram will then write up the entire adventure as an epic poem with Gilgamesh as the hero. The Doctor and Ace return to the TARDIS and depart, but in the Vortex, the Doctor picks up a strange reading on the time path indicator -- it appears as though the TARDIS is on a collision course with itself. Ishtar then materialises on board, having successfully incorporated the jettisoned TARDIS circuits into herself, and the Doctor realises too late why he warned himself about the Timewyrm -- because he created her. Qataka has become a living time machine, a threat to the Universe far more powerful and dangerous than Ishtar could ever have been. As she is still linked to the TARDIS, the Doctor tries to Time Ram her and destroy them both, but the Timewyrm flees into the Vortex, vowing revenge. Furious with himself, the Doctor sets off in pursuit...