The intro describes the major events that led to the current situation in the Solar System. Shortly before the 22nd century, humanity suffered several catastrophes, the major one being the AI Wars. As a result, all AI development has been banned by the ISA with the exception of a single AI controlling interplanetary shipping. Not long after that, a wormhole was located near Mars. Ten years later, the ISA sends a massive colony ship, the Noah's Ark, through the wormhole, almost immediately losing contact with the ship. The wormhole collapses, and the Ark is presumed lost with all hands. By 2080, ISA has been engaging in a constant legal battle with the megacorporations, who seek more freedom in exploring/exploiting other planets. Realizing that the corporations are winning, ISA forms the Confederate Fleet to maintain order throughout the system. A little less than a decade later, full-scale war breaks out between ISA and the megacorporations with the megacorporations emerging victorious. ISA retreats to Earth, enforcing its laws only as far as the Moon, leaving the rest to corporations.
The game's main character, Marcus Cromwell, is the son of Richard Cromwell, the first human born in space and the captain of the ill-fated Noah's Ark. His ISA ship is shot down by corporate forces near Phobos and is left drifting for nearly ten years as a Human Popsicle. After the war, he is found, revived, and hailed as a war hero, despite his side losing. He receives an offer from SpaceTech to take command of one of their corvettes, the Stiletto. His first mission takes him to Jupiter, where he saves an old ISA friend from OSEC (a rival corporation) forces. Later, Cromwell is ordered to intercept a freighter belonging to Kissaki Syndicate. During the encounter, the Stiletto crew witnesses a large ship of alien design meeting with the freighter. After locating and infiltrating the major Kissaki research center, an asteroid-based station named Shukenja, Cromwell finds the alien cruiser seen before inside the base. After commandeering the Angelwing (name of the cruiser), SpaceTech scientists discover the location of another base near Pluto. Since the Stiletto would take years to reach Pluto, Cromwell takes command of the Angelwing and uses its advanced interplanetary drive to reach the base in just several weeks. While scanning the base, an illegal AI uploads itself to the Angelwing and urges Cromwell to take the ship through a nearby wormhole in order to escape a malevolent alien entity attacking the ship.
On the other side of the wormhole, Cromwell discovers a thriving human colony, settled by the Noah's Ark. The inhabitants of the Noah colony serve as soldiers for a highly-advanced race of Technical Pacifists called Vardrags, who have discovered that Humans Are Warriors and are using them to fight a war against the Reptilian Gorgs, all of whom are Proud Warrior Race Guys. In return, the Vardrags share some of their technology. From Angel (the AI that uploaded itself to the Angelwing), the humans find out about the Mechanoids, a race of alien AIs who have destroyed their creators and are in the process of restructuring the very fabric of reality for their own benefit (wormholes are a side effect of this). Cromwell returns to the Solar System and finds a planetoid-sized sphere hiding behind the Moon. The Mechanoids have already wiped out everyone in space and are looking to infiltrate and take over Earth. Fearful, the Vardrags lock down the wormhole to the Solar System, forcing Cromwell to remain. He decides to join the fight against the Gorgs and leads several successful attacks against them. Eventually, the two sides agree to a ceasefire in order to focus their attention on the Mechanoids, who have taken over the Vardrag homeworld. Unfortunately, the Mechanoids are largely immune to traditional weapons.
After encountering a Horde of Alien Locusts whose energy-draining weapons appear to be effective against Mechanoids, Cromwell kills the ship-sized queen, and the Noah researchers use her to create the Energy Skeeter, capable of disabling Mechanoids, and later, the Anti-Mechanoid Shield, which destroys them within a large radius. Armed with these weapons, Cromwell leads a fleet back to Earth to free it from Mechanoid control, leading to the most intense battle in the game against several large Mechanoid-controlled fleets. Then Angel takes the Angelwing through a wormhole to a Negative Space Wedgie known as the titular Nexus. In order to destroy the Nexus, Cromwell has to close all wormholes leading to it, while dodging attacks by a Mechanoid-controlled Vardrag city-ship. Angel then leaves the ship and attacks the Nexus itself, destroying all Mechanoids within. The ending cutscene shows Cromwell back on liberated Earth meeting the godlike Angel at Stonehenge, who is departing to destroy all remaining Mechanoids.