Infinite Space begins as Nia Lochlain, a "launcher" who helps people leave their homeworlds to travel in space, assists her client Yuri leave his homeworld Ropesk and break the ban on space travel there. Ropesk's ruler Demid Panfilov takes Yuri's sister Kira hostage to force him to return. Yuri pawns his Epitaph, a gift from his father(that's what he thinks), to buy his own ship, then confronts Panfilov and rescues Kira. Sometime later, Yuri hears that the pawnshop holding his Epitaph has been attacked by pirates. He pursues the pirates, but is unable to prevent the legendary pirate Valantin from taking his Epitaph. Next, Yuri helps the Interplanetary Union of Elgava defeat the local pirate faction and is invited by Commander Oleg Vladykin to research Epitaphs in Elgava Central. There, Vladykin informs Yuri that an Elgavan probe ship studying Epitaphs has disappeared; Yuri verifies the ship was destroyed and learns that Epitaphs are sometimes found near Dead Gates. After a trip to Kalymnos examine the ruins of the Dead Gate planet Mytilene, Commander Vladykin alerts Yuri that a fleet traveling from another galaxy was what destroyed the Elgavan probe ship, and this fleet's destination is the Small Magellanic Cloud (SMC). Nia reveals to Yuri that the fleet belongs to the distant Lugovalian Empire and is vastly more powerful than the combined forces of the entire SMC.
Yuri then travels to the Spetses sector to rescue the kidnapped granddaughter of a prominent Nova Nacio industrialist, but encounters the pirate Valantin in ruins on Spetses that match those found on Mytilene. Valantin gives Yuri the Spetses Epitaph, which transforms and reactivates a nearby Dead Gate. Yuri follows Valantin through the restored Void Gate into Flux space, a region of space that constantly fluctuates into different states of existence. Valantin escapes and Yuri loses consciousness, reawakening in the remote Irvest sector. Yuri journeys to the Magellanic Stream to allow Nia the chance to warn the nations of the Large Magellanic Cloud about the Lugovalian invasion fleet, then is forced to choose sides in a war between Kalymnos and Nova Nacio over the Irvest sector. While Yuri works to end that conflict, Elgava makes contact with the Lugovalian fleet. Having greatly underestimated the Lugovalians' power, the Elgavan contact force is easily destroyed and Elgava falls days later. The defeat of the most powerful nation in the SMC prompts Nova Nacio to surrender to the Lugovalians immediately, while Kalymnos puts up a futile resistance.
With the entire SMC now subjugated by the Lugovalian Empire, Yuri and Nia travel to the Magellanic Stream to request the aid of the LMC nation Regeinland. The Lugovalian fleet arrives at the Magellanic Stream but is intercepted by a force from Regeinland. Lacking the strength to engage the Lugovalians, the Regeinlandics decide to seal off the starlane to the LMC. Yuri leads an attack on their fleet and manages to cripple their flagship. Nia boards the flagship and is mortally wounded while attempting to kill the Lugovalian commander. Meanwhile, the Regeinlandics deploy a prototype "exalaser" and cause a nearby red giant star to go supernova, wiping out much of both fleets and enveloping the Void Gate that leads to the LMC. Yuri and his remaining crew escape to the LMC before the Void Gate is sealed.
The second half of Infinite Space, subtitled "Yuri the Man", begins 10 years after the Lugovalian conquest of the Small Magellanic Cloud. The Galactic Federation of the Large Magellanic Cloud has suppressed all information about the fall of the SMC and imprisoned all SMC refugees, but the Lugovalian Empire is close to discovering a new route to the LMC. Yuri has been imprisoned on the prison asteroid Lari, but manages to escape with some friends and later rescues his old crew. Soon after he is surrounded by fleets from the nations of Libertas and Regeinland and chooses to surrender to the Regeinlandics, who enlist Yuri to help them prepare for the Lugovalians. As a test Yuri is asked to resolve a civil war in the frontier nation of Escondido, where he obtains another Epitaph. Regeinland then sends Yuri to investigate a newly-discovered Void Gate which may link to the SMC. Yuri uses the Epitaph to stabilize the Void Gate and takes it to the Spetses sector in the SMC, where he reunites with more of his old crew and reconnoiters the Lugovalians for the Regeinlandic military. Upon his return to the LMC, the fate of the SMC is made public and the LMC nations begin fortifying their borders. Libertas promotes an unpopular resolution to unify Galactic Federation members under a single government to fight Lugovalos. Coupled with news of a premeditated attack by Libertas against a small defenseless nation, the Federation becomes divided against Libertas and civil war breaks out. Regeinland heads a coalition of nations to assume control of the Federation and commissions Yuri to subdue two of Libertas' allies. With Libertas isolated, the balance of power shifts in Regeinland's favor.
Regeinland proceeds to move against the Orders group, the hardliner element of Libertas and the Federation. Once Orders' fleet is defeated, Libertas backs down and concedes to the Regeinland-led nations. The Federation president summons representatives from all Federation nations to the capital Merylgild, and a defense plan to confront Lugovalos is unanimously passed; for the first time in its 500 year history, the Galactic Federation is truly united. Despite being prepared, when Lugovalos finally invades the LMC, the Federation fleet guarding the Void Gate to the SMC is routed and surrounding sectors are captured. During the defense of the Andalucia sector, Yuri realizes he has the power to manipulate Flux sectors and in effect alter the reality within them. Later, Federation forces claim a decisive victory over a significant detachment of the Lugovalian fleet, slowing their advance through the LMC. Meanwhile, the Holy Nation of Adis begins claiming responsibility for the disappearances of ships using Void Gates. Yuri, now a hero of the Federation, leads a force to conquer Adis and end the supposed threat. Afterward, Patriarch Bogd of Adis reveals to Yuri the existence of the Overlords, omnipotent entities who create universes. The Overlords revealed themselves to the first humans, the Progenitors, on Terra thousands of years ago, bestowing the technology to travel faster-than-light and endure the rigors of space travel. Once humans had expanded throughout the entire universe, the Overlords would initiate the End of Days. Bogd explains that Yuri has his powers over Epitaphs and Flux sectors because he is an Observer, created directly by the Overlords; Kira is not Yuri's sister, but a Tracker created to trace Yuri's movements. The Void Gates collected the experiences of Observers and Trackers for the Overlords. At the site of the Ark of the Progenitors, Bogd tells Yuri that the Lugovalian emperor, Taranis, was also an Observer, and the reason for Lugovalos' conquest was to unite humanity to oppose the Overlords. When attempting to access the Overlords' network to discover how to defeat them, Kira is erased from existence, her body reduced into a dead android and an Epitaph.
Meanwhile, the Lugovalians continue strengthening their positions. Unable to negotiate with them, Yuri uses Kira's Epitaph to open a Void Gate into the SMC to assault Emperor Taranis' flagship. Yuri breaks through the Lugovalian main fleet and defeats Taranis, forcing him to retreat. Taranis then orders a ceasefire and peace talks between Lugovalos and the Galactic Federation are opened. Suddenly, Overlord ship-like entities called Phages appear and begin attacking everything in sight; the Phages' purpose is to break the universe down into dark matter and prepare for the creation of the next one. As more and more Phages arrive and begin dismantling planets and Void Gates shut down, Yuri escapes with the timely help of Valantin. At Merylgild, Valantin explains that the only way to stop the Overlords from destroying the universe is to find the "True Warp Gate" that connects to their dimension and close it. Information from the Kira-android confirms the Gate itself is in the Solar System, the long-lost birthplace of humanity. Yuri, Valantin, Taranis, and other people Yuri has met along the way travel to the Solar System using the Void Gate frame built into Valantin's ship. Near Mars, Valantin sacrifices himself to let Yuri destroy the True Warp Gate, which is in orbit around Terra and powered by a Dyson sphere encapsulating Sol. While Yuri fights off Phages, Taranis crashes his ship into the Dyson sphere, destroying it and closing the gate. The game ends as Yuri's ship slowly approaches a Flux sector, Yuri cradling the Kira android in his lap. After the credits, Yuri's ship is seen heading away from the now-stabilized Flux sector and Kira is briefly shown to have been restored. It is unknown if Yuri used his power to alter anything else in the universe.