The first main plotline follows the adventures of the passengers of the no-ship used by Sheeana and Duncan Idaho to flee from Chapterhouse as a result of Sheeana's disagreement with Bene Gesserit leader Murbella's plans for the Sisterhood. The second plot involves Murbella's attempts to unite the Bene Gesserit and Honored Matres, while conquering rebellious factions of Honored Matres on various planets and attempting to prepare for a confrontation with an Ancient Enemy. This unknown enemy was responsible for driving the Honored Matres back into the Old Empire.
For several years, the no-ship (named the Ithaca by its passengers) has been in an alternate universe, carrying the gholas of Duncan Idaho and the famous military commander Miles Teg as well as the Bene Gesserit Sheeana, who has the mysterious power to control sandworms. Other passengers include the last Bene Tleilax Master Scytale, some Bene Gesserits, a group of Jews saved from Honored Matre oppression on the planet Gammu, and seven small sandworms that can produce spice. Finally, there are four captive Futars, fierce half-man/half-cat creatures bred to hunt Honored Matres. The mysterious Oracle of Time speaks to Duncan and brings the no-ship back into the 'regular' universe. However, it is soon discovered by the mysterious "old man and old woman", Daniel and Marty, first mentioned at the end of Chapterhouse Dune, who have unknown designs on the Ithaca and its passengers. The no-ship is nearly caught in their tachyon net, but escapes using the space-folding Holtzman engines.
Meanwhile, Murbella is trying to prevent civil war on Chapterhouse, the only known source of melange left in the universe (other than the sandworms on the no-ship). She meets an emissary sent by the Spacing Guild, which is desperate for spice. Murbella refuses their requests due to the help the Guild gave to the Honored Matres, and demands the Guild's future loyalty, threatening to cut them off completely. Later, Murbella stops a brutal fight between some polarized Bene Gesserits and Honored Matres.
Though the Honored Matres had destroyed all Bene Tleilax worlds, their descendants (the Lost Tleilaxu) have returned from The Scattering. Supposedly under their complete control are their improved Face Dancers, creatures who can mimic other humans exactly and go undetected by all known means. It is soon revealed that the Face Dancers have their own will and motives, as they kill the Tleilaxu Elder Burah and replace him with their own duplicate. They have now replaced all the Lost Tleilaxu Elders, as well as countless humans on various planets in the Old Empire. Their leader Khrone sends the scribe Uxtal (presumably the highest-ranking, if only, Lost Teliaxu left alive) to serve the renegade Honored Matre leader Hellica, who has proclaimed herself Matre Superior and now rules the conquered Bene Tleilax homeworld, Tleilax.
The desperate Spacing Guild Administrators go to Ix to find an alternative to the use of their own Navigators (who require spice) for space travel. Unbeknownst to the Ixians or the Guild, Khrone and his Face Dancers have infiltrated Ix. While carefully executing his own plans for Face Dancer domination of the universe, Khrone is doing the bidding of Daniel and Marty by offering their advanced navigation technology to the Guild as if it were of Ixian design. The Guild agrees to the development of this technology if they have a monopoly on it.
On Tleilax, Uxtal has been forced (by threat of death) to use Tleilaxu axlotl tank technology to produce the adrenaline-enhancing drug used by Honored Matres. Khrone also tasks Uxtal to make a ghola from recently-found cell samples, which turn out to be those of Baron Vladimir Harkonnen. From the start, the young Baron is as sociopathic as the original. Later, Khrone obtains the blood of Paul Atreides from a religious relic on the Atreides homeworld once known as Caladan, and has Uxtal make a ghola of Paul. He plans to twist this Kwisatz Haderach ghola (using the Baron Harkonnen ghola) into a weapon for Daniel and Marty's conquest of the universe. Later, the Guild Navigator Edrik comes to Tleilax seeking Uxtal's knowledge of axlotl tanks; the Navigator fears his kind's obsolescence when the Ixian navigation technology becomes available. He seeks an alternate source of spice to break the Bene Gesserit monopoly, but even Uxtal believes that secret has died with the Tleilaxu Masters murdered by the Honored Matres. Eventually he is able to access the genetic material of deceased Master Waff, and through an accelerated process creates several (ultimately flawed) Waff gholas, hoping to unlock the secret of producing melange in the tanks. The entire universe is unaware that in the events of Chapterhouse Dune, Scytale had been forced to give the passengers of the Ithaca the secret, and it was in use on the no-ship as their primary source of spice.
On the Ithaca, Scytale is desperate. The Tleilaxu had always sustained their lives indefinitely through the use of gholas; his current body is slowly dying, and he does not have another to replace it. Needing to grow a new ghola of himself, he has only one secret to use as a bargaining tool: a hidden nullentropy capsule containing cells carefully and secretly collected by the Tleilaxu for millennia, including the cells of Tleilaxu Masters, Face Dancers, Paul Atreides, Duke Leto Atreides, Lady Jessica Atreides, Chani, Stilgar, Leto Atreides II, Gurney Halleck, Thufir Hawat, and even legendary figures dating back to the Butlerian Jihad, including Serena Butler and Xavier Harkonnen. The Bene Gesserit have a vicious debate over whether to create gholas of any of these historical figures. Sheeana believes they may prove useful, while others fear the return of such 'mistakes' as Leto II. Despite the controversy, gholas are created, a few at a time. Scytale is allowed to have his own once the first few have been born.
On Chapterhouse, Murbella trains an elite strike force of Bene Gesserit using the combined skills of Bene Gesserits, Honored Matres and 'lost' Sword Masters of Ginaz. Her 'Valkyries' attack the rebel Honored Matre strongholds on other planets with success, in the process discovering that some of the Honored Matres are Face Dancers in disguise, undetectable until death. A former Honored Matre herself, Murbella eventually accesses the Other Memory from her Honored Matre ancestors, and learns their true origins. The core of the Honored Matres were vengeful Tleilaxu females, freed and assimilated by Fish Speakers and Bene Gesserits fleeing in The Scattering. The Tleilaxu women had been used as axlotl tanks by their males for millennia; though the current Honored Matres did not know their own origins, this explains to Murbella why they had been compelled to so mercilessly annihilate the Tleilaxu worlds in the Old Empire. Murbella also 'remembers' the attack by a renegade Honored Matre that first antagonized the Enemy.
On the no-ship, an attempt by rebel Bene Gesserits to murder the Leto II ghola is foiled by the child himself, seemingly able to change into a sandworm at will. The Paul ghola wants to remember his past; with the help of the Chani ghola, he steals and consumes an overdose of spice. This fails to awaken his past memories, but instead he has a vision in which he has been stabbed by another, evil Paul Atreides. After being discovered by the Bene Gesserit, he concludes that it is prescience. Sheanna’s own visions bring a warning from the legendary Sayyadina Ramallo of Arrakis about the use of the gholas. She stops the ghola program from continuing until she can make sense of it all.
Daniel and Marty inform Khrone that they have no further need of his Baron Harkonnen and Paul Atreides gholas. They insist they have lured the Ithaca into a trap, and will soon have the Kwisatz Haderach they have calculated is on board. Khrone, however, continues to prepare the gholas. He finally manages to restore the Baron's memories, and instructs him to train the Paul ghola (named Paolo), who does not yet have his memories. To the Baron's disquiet, he finds the mocking voice of his granddaughter Alia in his thoughts soon after recovering his memories. She also later threatens him should he try to harm Paolo.
Murbella contracts Ix's competitor Richese to provide as many armed ships, and as much weaponry, as possible, in preparation for the confrontation with the unknown enemy. Later, the Honored Matres destroy the entire planet of Richese to cripple the Sisterhood. In a final assault on Tleilax, the most powerful of the rebel Honored Matre strongholds, Murbella and her Valkyries are victorious. It is revealed that Matre Superior Hellica and several of her elite guard were, in fact, Face Dancers. Many of the surviving Honored Matres then join with Murbella. Uxtal and the sole remaining Waff ghola each attempt to escape during the chaos. A Tleilaxu farmer gleefully allows "Master" Uxtal to be devoured by hungry sligs, while Waff finds refuge with the Spacing Guild, offering Edrik something better than artificial melange — the genetic knowledge for the Guild to create their own, optimized sandworms.
The Ithaca stumbles upon the homeworld of the Handlers, masters of the Futars. An exploratory party from the no-ship returns the man-beasts, and soon discovers that the seemingly bucolic Handlers are actually Face Dancers, tasked with their capture. Sheanna and her companions barely escape with their lives. Some Face Dancer ships manage to crash into the Ithaca before its escape, and potentially missing bodies in the wreckage have the no-ship's passengers wondering if the enemies are now among them. The emergency forces Miles Teg to reveal his hidden power of superhuman speed, unlocked in him during torture by Honored Matres in Heretics of Dune. He has kept this ability secret because the Bene Gesserit are suspicious of any males having any 'wild talents', lest another Kwisatz Haderach be created. To them, Paul Atreides and Leto II were disasters never to be repeated.
Murbella, now in complete control of the Honored Matres and Bene Gesserit, prepares a defense against the forces of the Enemy, now identified by Other Memory to be thinking machines of Omnius, the machine overlord destroyed back in the ancient Butlerian Jihad. The Oracle of Time is then revealed to be the living consciousness of Norma Cenva, somehow also still in existence millennia after the Jihad.
The story concludes with Daniel and Marty revealed to be Omnius and the independent robot, Erasmus. Before its destruction, the Omnius incarnation on Giedi Prime had launched 5,000 probes capable of constructing new machine colonies on any planets encountered. One of these probes eventually intercepted a signal transmitted by the last remaining Omnius on Corrin before it too was destroyed. Its forces and Synchronized Empire finally reassembled, the new version of the Evermind is on the way back to the Old Empire to destroy all humanity.