The storyline of the game takes place "some time since the starship Voyager returned home". There is a peace between the United Federation of Planets and the Klingon Empire to the point of co-operation between the two interstellar powers that extends to engineering projects, and it is at this point in the story we are introduced to the focal point of the storyline of the game.
The Klingon Empire and the United Federation of Planets has combined their efforts to design and build a starbase. This starbase, named "Unity One", is, however, special in that it utilizes new technology that is capable of detecting cloaked starships "far into the Neutral Zone".
This is an unwelcome development for the Romulan Empire, who begin to plot and put into motion events to eliminate the threat presented by Unity One in typical Romulan fashion; by manipulating events and politics of the region to make it appear as if rogue elements of the Klingon Empire are attacking Federation outposts and planets, thus making the Romulan Empire look like a blameless bystander. This is achieved not only solely via political manipulation, but by the theft of Federation "Incursion technology" that, when a Romulan starship cloaks, the cloak itself projects a mirage of a predetermined vessel. Thus, a Romulan Warbird, when cloaked, will appear to be a Klingon Neg'hvar battlecruiser. However, the firing of Romulan weapons will betray the ruse, as it is not possible to disguise Romulan disruptor fire, nor the signature plasma torpedo heavy weapon. This detail even comes into play in a Romulan Empire mission, in which the player is instructed to "leave no survivors" due to this fact.
Eventually, the Romulan gambit pays off and Unity One is destroyed. The task of the player as the game progresses, is to begin in the service of the Klingon Empire, uncovering more and more of the plot line. This plot will take the player into the service of the Romulan Empire next, and then the Federation. In each set of missions for each empire, the player begins with the smallest of available ships of the "fast frigate" class. As the player progresses, prestige is earned with which the player can upgrade weaponry and/or purchase new ship classes.