The TARDIS brings the Doctor and Sam to Hyspero, an ancient world full of magic and stories. While the Doctor reads tales from the Aja’ib, an amusing book of weird and fantastic adventures, Sam goes exploring and finds a man with scaly alligator skin, Gila, chained up in a double-decker London bus in an old graveyard full of flesh-eating djinn. She brings the Doctor to the bus, which he recognizes as the transport of his old flame Iris Wildthyme. The Doctor pilots the bus to a pit in the desert where Iris has been trapped by wild dogs -- Gila’s, set upon her as revenge for her kidnapping him. Iris finally admits to Gila that she’s on a mission for the Scarlet Empress to reunite the Four, Gila’s old mercenary band. Gila agrees to accompany her for the sake of the adventure, but the Doctor suspects that Iris isn’t telling them the whole truth. His suspicions seem borne out when they are attacked at a desert cafe by guards of the Scarlet Empress, sent to spur on the expedition and monitor Iris’ progress.

After piloting Iris’ bus-TARDIS across the mountains -- and enlisting the aid of an insect-djinn, a kabukij, to escape from a sandpit -- the Doctor and his companions arrive in Fortalice, a town which refuses to tolerate anything which inspires change. They have arrived on the day of the Grand Fracas, when the town Executioner uses an emotional inducer to inspire the populace to bloodshed, ridding them of the emotional repression that has built up through the year. Iris is drugged and sold to the Executioner for public torture and execution. Sam and Gila are trapped outside as the citizens turn on each other, but are rescued by Our Lady of the Flowers, the only outsider whom the citizens tolerate, due to her mysterious ability to grow beautiful flowers and luscious fruit.

The Doctor, meanwhile, goes to the town library and forces the reluctant librarian to let him browse the books at random. The librarian tolerates him until he sees that the Doctor is carrying a copy of the Aja’ib; scandalised, he gasses the Doctor and turns him over to the glass Vizier. The Vizier turns the librarian into stone, confiscates the Aja’ib and forces the Doctor to watch Iris’ pending execution. The Doctor memorises the spells the Vizier chanted over the Aja’ib, and uses them to release a hydra from the book upon the town. As the townsfolk flee in terror, the Doctor releases Iris, but the furious Executioner uses his emotional inducer to generate a hallucination of a gryphon which battles the Doctor’s hydra. The Executioner is killed as the beasts battle, and the Doctor is knocked unconscious. Iris takes him aboard her bus and flees, leaving Sam and Gila to their fate -- much to the Doctor’s fury once he finds out.

The metal hands of the cybernetic Duchess, another of the Four, lead Sam and Gila out of Our Lady’s indoor jungle to an underground river, where disembodied voices haunt them with doubts, fears and literary analysis. They emerge in the forest of Kestheven, where they are captured by the hairless bears ruled by Major Angela -- the Bearded Lady, the third of the Four. The Doctor and Iris have also reached Kestheven, but have been captured by birds who demand to be told stories with a proper beginning, middle, end and moral. Iris slips away while the Doctor tells stories to the birds, but the guards of the Scarlet Empress track them down and set fire to the birds’ nests to spur on the expedition. Iris finds the Duchess waiting at the bus, and at her urging the Duchess rescues the Doctor from the burning nests from which the birds have already fled. They return for Iris only to find that she has fainted -- and the depth of her “faint” confirms the Doctor’s suspicions that there’s more to her weakness than she’s letting on.

Major Angela, shocked by her unexpected reunion with Gila and the Duchess, admits that the Scarlet Empress is really after the body of Cassandra -- the preserved and still-living embodiment of the first Scarlet Empress. Iris, meanwhile, has an out-of-body experience and sees the current Empress plotting to send her daughter Julia in the pirate ship Kristeva to capture the expedition once it reaches the sea. She recovers to find that the Doctor has sat up with her all night, and, touched, she admits that she is dying -- and that she has made a deal with the Scarlet Empress to cure her if she keeps her side of the bargain and returns Cassandra.

Angela doesn’t want to leave her kingdom, but is forced to concede that the Scarlet Empress will never leave her alone now; the current Empress is power-mad and won’t rest until she rules all of Hyspero and has separated it into easily classifiable and controllable sections. At the Doctor’s urging, Angela releases the spirit of Cassandra from her jar, and Cassandra agrees to help them stop the current Empress, who has brought the name of their dynasty into disrepute. Before confronting the Empress they must fetch the last of the Four -- the Mock Turtle, who is imprisoned in a land of ice and snow beyond the next gateway. The worlds have been separated by the Scarlet Empress, who has set a giant spider to guard the gateway, but the Doctor convinces the spider to join their expedition and fight the cruel Empress.

In the snow arena, the spider and the Duchess -- the two least human of the party -- fall in love and merge into a symbiotic entity which fights off a giant walrus sent by the Empress to attack the expedition. Gila, who is beginning to revert to an animalistic alligator state, fires a cannon at the fighters, killing the walrus and grievously injuring the Spider Duchess. The wounded Spider Duchess remains behind to recover if possible and to hold off the pursuing guards, while the others carry on and awaken the Mock Turtle from his prison. But they are all captured by the pirates of the Kristeva, and the Mock Turtle summons an unusual sort of help -- the oldest fish in the world rises and swallows him, Iris, and the Doctor. The Doctor demands to be let out, and the fish spits out its passengers on a desert island. Iris’ bus drives under the sea to her rescue, and the Doctor prepares to pilot it back to the Empress’ palace for the final showdown -- but Iris faints for what may be the last time, and her body enters a healing coma.

Angela admits to Sam and Gila that she stole Cassandra’s jar to seek the answers to the great questions of life, but all Cassandra has ever done in reply is laugh. The Kristeva launches into the air to return to the palace, but it is attacked by the angry birds of Kestheven. Sam, Gila and Angela escape in a flying lifeboat as the Kristeva crashes into the sea, killing all on board. The lifeboat lands in the city of Hyspero, where Sam, Angela and Gila are captured by palace guards and taken before the Empress. But as the Empress confronts them, demanding the return of the jar, Iris’ TARDIS materializes in the throne room. To the Empress’ horror, the Doctor releases Cassandra, who informs the current Empress that she has sullied the name of the dynasty, and sets out to restart time again and clean up the mess left by the last few Empresses. Gila loses all humanity and becomes a full-blooded alligator, while the Doctor and the others shelter out the remaining changes inside Iris’ bus.