A radio telescope detects the approach of a large asteroid on a collision course with Earth; authorities dub it "Attila" after the ancient conqueror Attila the Hun. Scientists determine explosives planted on the surface of the asteroid may divert it into a stable orbit around Earth. A five-person expedition uses the Space Shuttle Atlantis to rendezvous with the asteroid and plant the charges. The crew consists of Commander Boston Low (voiced by Robert Patrick); Dr. Ludger Brink (Steven Blum), a German archaeologist and geologist; Maggie Robbins (Mari Weiss), a linguistics expert and reporter; pilot Ken Borden (David Lodge); and NASA technician Cora Miles (Leilani Jones), who is also running for Congress.
Low, Brink, and Robbins spacewalk to the asteroid and set the charges. While they are successful in altering the orbit of Attila, they find the inside of the asteroid appears hollow, and proceed to explore. When they enter a central chamber, they are trapped as the asteroid transforms into a dodecahedron pod and rapidly accelerates away into deep space. When the three recover and can exit the pod, they find themselves on an alien planet, on a central island surrounded by five smaller, spire-shaped islands; in the game's novelization, they name the planet Cocytus. It shows signs of former intelligent life, but as they explore, they find no evidence of any sentient creatures that remain, and the one advanced complex they are in shows signs of long-term deterioration. They encounter a strange form of spirit-like energy that guides them to a particular patch of ground, which they find to be soft and consistent with an opening that has been buried by time. Shortly after Brink begins digging, the ground gives way beneath him, opening a cavern into a subterranean structure. Robbins and Low find Brink dead at the bottom of the rubble.
Robbins insists they explore the structure separately and the two part ways, keeping in contact with their communicators. In what appears to be a museum, Low discovers a pair of crystals containing a glowing green liquid. After seeing a demonstration in the museum of similar crystals being used in what looks like a resurrection ceremony, Low tries one on Brink, bringing him back to life. They search for a means to return to Earth, using Brink's and Robbins' talents for xenoarchaeology to decipher alien text and images.
As the trio continue to explore, they find Brink has become addicted to the crystals and started hoarding them for himself, leading to conflict within the group. Low discovers a pyramid that houses a preserved alien, whom he is able to reanimate by use of the life crystals. Through Robbins, the alien explains that his species had become obsessed with eternal life and had decided to travel to a new universe, Spacetime Six, from the current one, which they call Spacetime Four. The alien chose to remain behind to warn others about the crystals and the dangers of transcending to Spacetime Six. However, the rest of the species have been unable to find a way to return to Spacetime Four, and only they would be able to provide the humans with a spacecraft to return to Earth.
Low offers to travel to Spacetime Six to show the aliens how to return, but this requires them to repower the portal that was used. They are able to retrieve two life crystals from a machine that generates them, but Low and Brink fight over the crystals, and Brink falls to his death. During the process of opening the portal, Robbins is killed. The player has the option of reviving Robbins with a life crystal after the portal is opened; however, if they do, she immediately jumps to her death, with no crystals left to revive her a second time. With no other options, Low uses the portal to meet the rest of the aliens in Spacetime Six; with the portal open, the aliens can perceive the route home and return to Cocytus. They restore Brink and Robbins to life and cure Brink of his addiction to the crystals, though this leaves him as an elderly man. If Low left Robbins dead, she is happy to see him, but if Low revived her, she is angry and scorns him. As promised, the aliens reconstruct a spacecraft for the humans, and representatives of the species join the humans as they return to Earth.