Earth struggles with overpopulation and starvation, and even though humans have gained access to the mysterious Heechee technology, including their faster-than-light spaceships, this has not done much to mitigate these issues. A "food factory" spaceship, long abandoned by the Heechee, is found deep in the Oort cloud, and an expedition funded by Robin Broadhead, a millionaire former Gateway prospector, is sent to investigate. The crew, a family of four, is astonished to find a young man, Wan, occupying the spaceship. Wan tells how he grew up alone on Heechee Heaven, a faraway space station and of how he regularly visits the food factory for supplies and entertainment in his small Heechee spaceship. He is as ignorant about social cues as he is about the inner workings of Heechee technology. The youngest crew member, teenage Janine, is enamored with Wan, as he is the first young man she has seen since their four-year voyage started.

Wan shows Janine around the food factory, introducing her to the dreaming chamber. Wan's repeated usage of the dreaming chamber coincides with semiannual outbreaks of a mysterious planet-wide fever that has hit Earth regularly over the last decade, and the crew quickly realize that Wan's dreams and nightmares are somehow psychically projected at the population of Earth at lightspeed, causing the "130-day fever". Janine briefly tests the chamber herself before her father and brother-in-law dismantle it.

Meanwhile, status reports are streaming back to Earth at lightspeed, creating a 26-day lag in communications for Robin Broadhead. Wan's final use of the dreaming chamber causes accidents worldwide, including one which severely injures Robin's wife Essie; Robin's time becomes divided between worrying about his wife and worrying about his crew. Robin's motivations seem altruistic instead of financial--he genuinely hopes to use Heechee technology to feed the starving billions of Earth, but secretly he hopes to use the food factory to master Heechee technology such that he can rescue his lost love Klara, whom he stranded years before in a Heechee ship in a black hole at the conclusion of Gateway.

Wan leaves the food factory with Janine, her older sister Lurvey, and brother-in-law Paul in his Heechee spaceship, headed for Heechee Heaven. He tells the crew Heechee Heaven is home to Old Ones, who the crew assume are Heechee, and the "Dead Men", who seem to be self-aware computer recordings of the personalities of dead, human Gateway prospectors who can communicate with the food factory via FTL radio; the Dead Men are Wan's only friends. Due to space constraints they leave old Payter, the father of Janine and Lurvey, behind alone at the food factory. Robin Broadhead is excited and terrified about a physical encounter with the Heechee, even from so far away.

On board the giant Heechee Heaven station, the explorers interrogate the Dead Men, finding them barely sane and mostly useless. The Old Ones capture Wan, Janine, and Lurvey. They are each subjected to a device like the dreaming couch, where they relive memories of dozens of dead Old Ones, with the oldest memory being that of a creature that is not a Heechee, but rather one that was captured by Heechee scientists more than half a million years ago for study on Earth--an Australopithecus, an ancestor of modern man. The missing Heechee left a colony of Old Ones onboard Heechee Heaven in the care of a machine intelligence of an ancient Old One, hoping that further intelligence would evolve in the species if shepherded carefully. The Old Ones are gentle and intelligent, possessing language and rudimentary culture, but are relatively dimwitted compared to men, and live in fear of the mechanical Oldest One, who they consider a god.

Transmissions from Heechee Heaven (via the FTL radio of the Dead Men) ends with the capture of the explorers. Payter, on board the food factory, quickly goes mad, realizing the severity of his situation: alone on a small space station years away from rescue. At his age he knows that alone and without the diagnostic medical equipment his crewmates took to Heechee Heaven, he will not survive the four-year return trip to Earth. Greedily he reconnects the dreaming chamber, broadcasts a spiteful ultimatum at Earth, and causes the worst outbreak of the 130-day fever yet. On Earth, Robin's wife recovers, and gives him permission to personally go to Heechee Heaven to save his crew and to somehow stop Payter. During another round of Payter's 130-day fever, Robin steals a Heechee ship on the Moon, filling it with computer equipment (to interrogate the Dead Men) and weapons (to subdue the Old Ones), and heads to Heechee Heaven.

Robin and Paul meet and rescue the captives using stun rifles. The Oldest One, unsure of what to do about the chaos set into motion by the intruders, has launched Heechee Heaven on a course seemingly to the black hole at the center of the galaxy, desiring the advice of his unknown creators. Subduing the Oldest One, Robin and Paul take control of Heechee Heaven. Robin's wife Essie, a computer programmer, has built an algorithm to simulate the husband of Henrietta, one of the Dead Men. They use this to trick Henrietta into revealing how much of the Heechee technology operates. Armed with such information, they take Heechee Heaven into Earth orbit via FTL travel.

The crew become fantastically wealthy from their voyage; Robin, the richest man in the solar system. Happy with his healthy wife, his secure finances, and his slow but certain resolution of the food crisis on Earth, he is still terrified of the Heechee, and where they may have gone. Albert, an AI scientist program written by his wife, conjectures that the Heechee may have hidden themselves inside a black hole, taking advantage of relativistic time dilation to live quiet lives at a much slower rate than outside of the black hole's singularity. Robin becomes more convinced that he can rescue his lost love Klara, if the Heechee can indeed travel in and out of black holes. Albert philosophically discusses the implications of such technology with Robin. He suggests the Heechee may have hidden in a black hole on purpose after tampering with the fabric of spacetime such that the entire universe would collapse on itself, starting over in a new Big Bang with a fundamental physical reality more suited towards intelligent life in some unknown fashion, exiting their protective black hole when conditions had become satisfactory. Robin shudders in terror at the notion of beings with such ambition and power.

The final chapter of the novel is told from the perspective of a Heechee "Captain" who led the Australopithecus project on Heechee Heaven and the various expeditions to Earth. He and all of his kind are indeed hiding inside a black hole at the center of the galaxy. Albert, the AI, is right and wrong: the fabric of the Universe has indeed been tampered with, but not by the Heechee. When the Heechee discovered this, they went into hiding, using gravitational manipulation technology to create a black hole around a large cluster of captive stars and planets. The Captain muses that the Australopithecus species (and some 15 other similar project races across the galaxy) are to the Heechee as the Heechee are to the mystery race who will reshape the entire Universe. He hopes that one day these project races will develop intelligence and travel the stars, not for any intellectual or cultural pleasure, but rather to act as buffer states between the Heechee and those mysterious others.