This story starts in the year 2303, when Captain Irravel Veda of the starship Hirondelle is attacked by pirates. She considers activating the "greenfly" terraforming machines on board, which apparently are capable of defeating the pirates with ease. Unfortunately, she fails to do so and the pirates capture her. She is tortured to reveal the codes to her ship's cargo – twenty thousand colonists suspended in stasis – but refuses due to psychological conditioning that makes her see the cargo as her children and do anything to protect them. She wakes up on the Hirondelle some time later, having no memory of the interrogation. She find the pirates' interrogator, Mirsky, has been abandoned with her. Irravel does not trust her, but Mirsky removes the mind-control device that pirate captain Run Seven (known just as "Seven") was using to control her, earning Irravel's trust. They awaken Remontoire, one of the Conjoiners on the ship and use his expertise to track down the pirates and fight them in 2328. Mirsky kills Seven on the ship's surface, but Irravel is wounded and dies. Her body is saved and her personality is resurrected in the ship's computer, which is awakened whilst the Hirondelle is orbiting Yellowstone in 2415.
By 2658, Irravel has acquired a clone body of herself. Markarian, a crewmember of the Hirondelle that Irravel had surrendered to the pirates, has disappeared with the remaining colonists and is fleeing aboard the pirates' ship Hideyoshi. Still under the influence of her Ultranaut conditioning, Irravel gives chase, following him to the "Nestbuilder" race in 2931, who reveal that the Greenfly machines were taken to the star Ross 128 and have since malfunctioned, destroyed the planets there, turning them into trillions of domes filled with vegetation. The inhabitants of the star system were unable to stop them. Irravel says she cannot help the Nestbuilders and leaves. Mirsky dies in space in 3354. In their last conversation, they discuss the Greenfly, which has by now started spreading to other systems, destroying the intelligent races it was designed to support. All attempts at containing the swarm have failed.
In 4161, Irravel stops at the Pleiades cluster and meets the Conjoiners and Islanders on the planets in the star cluster. Markarian is still fleeing her. She learns that the Greenflies are now consuming whole star systems at a massive rate. The Islanders put on a play, in which Irravel (unknown to the islanders) plays herself. She leaves the next morning and eventually catches up with Markarian in AD 9730, by which point the Greenflies have wiped out most of human civilisation. The two ships view this from high above the Galactic Plane (Galactic North). They receive a message from Remontoire, who has managed to survive with a small group of Conjoiners by orbiting a pulsar (the Greenflies are not attacking pulsars as there would be no light to sustain vegetation). They meet the Conjoiners in AD 40,000 on Hope, a hollowed out asteroid the Conjoiners have ejected from the Galaxy. They explore the Hideyoshi and discover Markarian has been absorbed by the ship. They take the colonists (whom he has stored on a data disk as digital blueprints) and prepare to leave the Galaxy to re-establish a new civilization elsewhere.
The novel Absolution Gap contains a reference to entities in a parallel universe (or at least claiming to be from one) facing attack from an agent very similar to the Greenfly. In their world, the Greenfly gradually consume the entire universe, rendering it uninhabitable.