The game is split into 7 episodes, each with its own stand-alone story.
Upon reaching the planet and beaming down, the crew are warmly greeted by the colonists, but are informed that a recent encounter with a "gateway to hell" down in the mines and a subsequent mysterious avalanche had left one of their miners buried under fallen rocks. A rescue team was sent, but it was attacked by "demons", with one man severely injured. McCoy examines that injured man and determines that he is developing a serious infection, the cure to which is not available in the Enterprise's medical supplies. Fortunately, Brother Stephen, an amateur scientist among the colonists, points out that a plant that grows near the mines can be processed to produce the required medicine.
The team hikes up the mountains towards the "haunted" mines, but halfway there they are suddenly ambushed by a trio of Klingons. After a short firefight, the Klingons are all stunned. Curiously enough the Enterprise chimes in to report that it had detected the phaser fire - but no disruptor fire (the Klingons' preferred and only type of firearm). Furthermore, upon examining the fallen Klingons Spock discovers that they are not real - but rather organic constructs. Kirk collects the severed hand of one of these fake Klingons for later study, while McCoy collects the required plants and the team retreats to the colony to synthesize the medicine.
After healing the injured man, Kirk questions some of the colonists who've encountered the "demons" near the mines, and hears stories of a variety of different mythical/demonic beings attacking the miners. Each miner appears to have been attacked specifically by an evil creature from his own religious beliefs. Additionally, Brother Stephen relates the history of the planet to Kirk: Its moon was destroyed in a cataclysm many millennia ago, and meteor strikes caused the planet to undergo an ice age which has just recently begun to wane. He also explains that Pollux V was one of the few rare planets in the galaxy to experience full solar eclipses (when its moon was still around). Finally, Stephen shows Kirk his small collection of trinkets picked up from the surrounding area by his fellow colonists, some of which he believes indicate that the area used to be inhabited by an alien culture of some sort.
Returning quickly to the mountain, Kirk and crew finally enter the mines and discover the door that the colonists spoke of, a massive metal door of advanced make, blocked by rubble from the avalanche. Carefully clearing the rocks away with their phasers, the team discovers the trapped miner underneath, just barely alive. McCoy treats the miner and resuscitates him. With the door now cleared of obstacles, Spock discovers a hand-print identification panel next to the door. Kirk surmises that the panel might be opened using the hand of the fallen "Klingon", and has Spock repair it back at the colony. Sure enough, the hand opens the door, leading into a tunnel going deep into the mountain.
At the end of the tunnel, the team reaches what appears to be a massive alien life-support facility, currently keeping a large number of creatures in suspended animation. Figuring out that the machine is waiting for another eclipse that will never come, Kirk solves a puzzle embedded on the side of the machine, which requires aligning the planet with its sun and moon to form an "eclipse" pattern. This triggers the alien facility, raising a chamber from the floor, out of which climbs a strange reptilian creature that greets Kirk. The creature identifies itself as a Nauian - one of the original inhabitants of the planet - and tells the story of how his people put themselves into suspended animation in order to survive the ice-age caused by a meteor storm eons ago. He also explains that the machine is capable of scanning the minds of any potential intruders, learning their greatest fears, and creating organic constructs to resemble those fears and drive the intruders away from the facility. Unfortunately, the key that disables the machine is missing, and it cannot be turned off - potentially posing a risk even to the Nauians themselves.
Kirk, remembering Brother Stephen's collection, returns to the colony and picks up an interesting piece of twisted metal that is clearly of artificial origin, as well as a small skull of a local animal that resembles the slumbering aliens. He presents the skull to the Nauian, who confirms that the small non-sentient animals now roaming the planet must be the descendants of those Nauians who did not flee to the underground suspension facility. The twisted metal piece turns out to be the missing key, and the Nauian turns off the defensive computer once and for all. He thanks Kirk and expresses desire for the Nauians to join the Federation, which Kirk accepts eagerly. Kirk assures him that the Nauians and Federation colonists will easily get along together, especially given that both parties show a keen interest in theology.
When Kirk hails the ship, he is answered by Cereth, an Elasi pirate captain from the planet Menalvagor whose clan has spent the last three years waging a criminal/terrorist campaign against Federation targets under the guise of political revolution. Cereth announces that he has hijacked the Masada and taken her entire crew hostage. He demands that the Federation agree to release 25 of his compatriots, held in a Federation prison for heinous acts of piracy and murder - or else he will destroy the ship. Kirk attempts to convince Cereth to beam over for negotiations, but Cereth sees through the ruse (knowing he would have to drop his shields to beam over, and thus be open to a boarding action). Kirk is forced to acquiesce to the demand, if only to buy some time.
Studying the records in the Enterprise computer, Kirk discovers the Masada's prefix code and uses it to drop the Masada's shields for a brief moment - long enough to beam himself and his away-team into the ship. They arrive to discover severe signs of battle, and detect a powerful energy field blocking entry into the ship's bridge. After reviving a downed Masada crew-member, Kirk and Spock begin to formulate a plan to assault and take over the bridge without giving the Elasi time to execute their hostages. First they assault the brig, where most of the Masada's crew are being kept behind a forcefield, and take out two of the pirates in the process.
Examining the brig carefully, Spock discovers that the forcefield to the hostages' holding cell has been booby-trapped with a powerful bomb. He disarms the bomb, releasing the hostages. The now-freed crew-members reveal a sneaky way to disable the forcefield protecting the bridge, but Kirk instead opts to trust Spock's engineering skills. He instructs Spock to repair the Masada's damaged transporter system, so that it can be used to beam the entire away-team onto the bridge for a surprise attack. They scrounge many scrap pieces and tools from the disheveled corridors of the Masada, and Spock manages to jury-rig the transporter for a single use.
Kirk and the team beam themselves onto the bridge, taking the pirates completely by surprise. Despite his ruthlessness and cunning, Elasi Cereth is forced to acknowledge that he has been bested by Kirk's ingenuity, and surrenders himself and his fellow terrorists over to Kirk. An Enterprise security team beams over to take control of the Masada, and the mission ends in a resounding success.
Upon beaming over to the Ark-7, the away-team discovers that the Romulans have holed themselves up on the lower deck. Spock and McCoy delve into the station's records, and discover that the scientists had accidentally developed a virus called "Oroborus" that is deadly to both Romulans and Vulcans - which means that Spock is now also infected. According to the station logs, the scientists - avowed pacifists - intended to destroy both the virus and the research that led to its creation, but the Romulans attacked before they could do so.
The bulk of the mission involves Kirk and crew attempting to research a cure for the virus themselves. After some trial and error, it turns out that the virus is vulnerable to ammonia. McCoy synthesizes a cure using the station's advanced scientific machinery, and injects it into Spock. Additionally, Kirk synthesizes a small quantity of a substance called TLTDH, essentially a Romulan/Vulcan laughing gas, which he releases into the station's ventilation system to knock out the dying Romulans barricaded on the lower deck.
McCoy proceeds to inject the dying Romulans with the cure and free the hostages. The scientists explain to Ardea Preax that the virus was developed completely by accident, and that they had intended to destroy it all along. Thanks to Kirk's valiant attempt to cure the Romulans despite their hostile action, the Romulan commander accepts this explanation and agrees to stand down and return to Romulan space.
The away-team arrives in the derelict's cargo bay, where they discover Mudd rummaging through an incredible collection of alien artifacts. He admits to have been selling some of the more useful items around the sector, claiming them to be his own inventions. Kirk locates several interesting items and discovers that they can be combined. When he does so, the result is a dangerous hand-held weapon - explaining why the pirates have been so keen on finding the source of Mudd's merchandise.
The Enterprise leaves the vicinity to chase off several approaching pirate ships, leaving Kirk and his crew to explore the derelict further. They discover a unique, functional weapon system on board, and decide to later install it on the Enterprise to boost its firepower. They also discover an alien computer system, and after determining the aliens' mode of thinking, manage to decipher the controls and access the memory banks. Inside is a treasure-trove of information about the aliens themselves, as well as data on medical technology far advanced beyond the Federation's capabilities.
While the away-team is exploring the ship, Mudd himself causes no end of trouble. Messing with the ship's sick-bay apparatus he accidentally breaks a container of unknown gases, triggering a violent paranoid psychotic reaction in himself which McCoy must cure him of. Later on, he messes with the now-accessible computer in an attempt to download its valuable information, but instead only manages to wipe the entire database clean. Finally, the shoddy life-support system he had installed on board begins to malfunction, threatening the lives of both himself and the away-team.
When the Enterprise finally returns, Kirk confronts Mudd over his blunders - which have criminal ramifications - and coerces him to agree to donate five of each alien artifact found on the ship to a Federation research institute. Mudd protests but finally agrees, and the away-team beams back to the Enterprise, with Kirk holding in his pocket a partial copy of the alien computer's databases that he had cleverly downloaded earlier.
After sending their mission report back to Starfleet, Uhura informs Kirk that she's made travel arrangements for Stella Mudd to meet her long-lost husband on a nearby Starbase - as a small punishment for his misconduct.
At Zamphor, the planet at the end of the energy trail, the Enterprise encounters a Klingon cruiser. The Klingons explain that the "renegade" in question is actually a war criminal, charged with committing genocide on Hrakkour - erasing all life there. Kirk just barely manages to convince the Klingons to give the Enterprise some time to apprehend the renegade for them - hoping that he might save this criminal from summary Klingon "justice".
Kirk and his away-team beam down to Zamphor, and immediately encounter a powerful alien being calling itself "Quetzecoatl". As it turns out, this being is in fact the ancient Aztec god of the same name. When confronted with the Klingon accusations of genocide, and the atrocities committed by the Aztecs in his name, Quetzecoatl becomes angry and teleports the away-team into a pit elsewhere on the planet to "learn the error of their ways".
The away-team use their ingenuity to escape the pit, and follow a path of insect-powered lights deeper into the jungles of Zamphor, hoping to locate Quetzecoatl again. They pass several obstacles along the way, including an angry Aztec priest of Quetzecoatl as well as a giant squid monster lurking in the river underneath a fallen-log bridge. They finally arrive at Quetzecoatl's abode inside a dilithium crystal cavern, only to discover that Quetzecoatl was testing them to see whether they are truly as advanced as they had appeared to be at first.
At his abode, Quetzecoatl inquires about the fate of the Aztecs and laments the brutal evolution of their religion, claiming that his message of peace and self-sacrifice had simply been subverted. He speculates that the same thing must have happened to the Klingons on Hrakkour. Shaken by this revelation, Quetzecoatl expresses his desire to give up his powers - which are bestowed by a gland at the top of his spine. He asks Kirk to undergo surgery on the Enterprise to remove the gland. Kirk agrees, and the team beams back to the ship together with Quetzecoatl.
While the surgery is taking place, additional Klingon warships arrive at Zamphor, commanded by Admiral Vlict Kenka - high commander of the Klingon fleet. As Kirk tries to convince him that Quetzecoatl is not to blame for whatever happened to Hrakkour, it becomes clear that Kenka himself is the one who purged the planet of all life (including his own family, who were the ruling family of that planet), simply because Quetzecoatl's philosophy of peace had "corrupted" them all. Kirk wants to refuse Vlict's demands for extradition, but Starfleet contacts the Enterprise to let them know that the Organians had decreed that Quetzecoatl must face trial in a Klingon court. Fortunately, they had also decreed that Kirk could act as a representative at the trial. The Enterprise departs to Hrakkour for the proceedings.
At the courtroom on Hrakkour, it quickly becomes evident that Vlict intends to find Quetzecoatl guilty at all costs, to cover up for Vlict's own genocidal actions - which were not approved by the Klingon government. Kirk cites his own honor in past encounters with Klingons, and thus manages to convince Vlict to allow him and his team to go through the "Test of Life" originally prepared for Quetzecoatl to determine his guilt.
Kirk and the team are transported to an old section of the Klingon mines under Hrakkour. First, they must defeat an entity of pure electricity blocking their way forward, which Kirk does by melting some iron ore and coating a support beam with it, then throwing it at the monster to 'short it out'. After that, they contact the Enterprise to overcome a lock that appears to have been tampered with specifically to kill anyone trying to open it.
After completing this "test", the team find themselves in a room that is clearly of alien origin and was never discovered by the Klingons. Inside is a machine operated by colorful gems that, when placed in the correct sequence, call forth an entity called "Bialbi", an ancient alien caretaker. Bialbi decides to arbitrate in Quetzecoatl's case, teleporting Vlict into the room and confronting him with charges of genocide. Kirk intervenes, and manages to convince Bialbi to spare Vlict's life if Vlict promises to drop the charges against Quetzecoatl. Vlict agrees to this exchange, and Bialbi decrees that the Klingons will must never return to Hrakkour.
After this is done, Bialbi teleports the away-team and Quetzecoatl back to the Enterprise. They take Quetzecoatl back to Zamphor, presumably to live out the rest of his now-mortal life in the closest thing he has to a home.
Consulting with Spock and the ship's computer, Kirk learns a great deal about the ancient history and cultures of Proxtrey. The inhabitants of this world, once divided into two primary cultures, nearly destroyed themselves in a nuclear war a millennium ago, and are only now beginning to return to their previous level of technology. The current culture is very religious, and considers the asteroid in question to be their god of war, whom they call "Scythe". Kirk also learns that one of the warring cultures of the planet before its holocaust used the trinary system (base-3) in their mathematics.
Upon reaching the asteroid, initial scans reveal that it houses an ancient nuclear missile launch facility built by the Lucrs - one of the two ancient warring cultures of Proxtrey. Spock quickly surmises that this base may have been what destroyed the civilization on the planet below, and that the asteroid may in fact be Proxtrey's old moon - knocked out of orbit during the war. Based on this hypothesis, he deduces that the missile base may have become active again once the Proxtrians on the planet below re-invented the radio, and that it may now be preparing to fire its remaining missiles at Proxtrey.
While the bridge crew are debating this hypothesis, the Enterprise intercepts a message transmitted from the asteroid to Proxtrey. While Uhura gets to work translating the message, Kirk and an away-team beam down. Immediately after beaming, the transporter system on the Enterprise suffers a malfunction, prompting Scotty and his engineering team to start diagnosing the problem.
On the asteroid's surface, Kirk and team discover a massive door leading into an underground complex. Using his recently-acquired knowledge about numbers sacred to the old Lucr culture, Kirk manages to guess the access codes to the base's two outer doors, and the team enters the facility. However in the meanwhile, the problems up on the Enterprise begin to compound: Both the phaser banks and the tractor beam system - necessary to counter any potential missile launches from the base - have apparently succumbed to a Computer Virus that was uploaded to the Enterprise when it scanned the asteroid. Uhura, displaying remarkable knowledge in computer science, begins looking for solutions to the problem.
Inside they find a solid door with a keycard lock, and a mineshaft with a large laser drill. Spock scans the keycard lock and inputs the shape of the desired keycard into the laser drill, firing it to create a template. Kirk places some rocks from the asteroid's surface on top of the template, and Spock uses the drill again to melt them, creating a duplicate of the original keycard. This allows the team to open the locked door. While they do this, Uhura and Transporter Chief Kyle manage to remove the virus from the Enterprise computers by attacking it with a Klingon computer virus. However the affected systems are still damaged, and will not be able to assist if the base launches its payload.
Behind the locked door, the away-team discovers the base's nuclear missiles and launch computers. Two large, separate computers calculate the asteroid's position in the solar system and determine the optimal launch window for the missiles. However, Spock discovers that one of the computers is infected with a virus, and is calculating the wrong launch time. He determines that the solution to the problem would be to infect the other computer with the same virus, causing the missiles to launch at the wrong time, run out of fuel prematurely, and fall harmlessly into the sun. The team accomplishes this by finding some computer cables and hooking up the two computers to each other.
The U.S.S. Republic (the ship that fought a mock battle against the Enterprise at the very start of the game) reported twelve hours ago that it was under attack. The Enterprise arrives to investigate, but finds the Republic heavily damaged and adrift. Sensors detect only two crewmembers still alive on board, and no other ships in the area. Kirk hurries to beam over to the Republic in the hope of saving any survivors.
On the Republic, the situation is grim. The last crewmember alive on the bridge dies moments before the away-team arrives. The ship has no power, save for what little is keeping the life-support systems active. Accessing the last Captain's Log, the team hears a baffling report of another Constitution-class starship attacking the Republic for no apparent reason.
The team rushes down to Sickbay, one of the few accessible parts of the nearly-destroyed ship. There they find Brittany Marata, an old acquaintance of Kirk's from the Academy, dying on a medical bed. McCoy treats her to the best of his abilities, but with her last breath she accuses the Enterprise of destroying the Republic.
With the entire crew dead, Kirk resolves to try and restore power to the Republic, while the Enterprise moves off to assist a trader vessel transmitting a distress code in the vicinity. The away-team scrounges up several components and links the still-functional impulse engines into the ship's power-routing system. Next, they manage to unjam the malfunctioning door to the Auxiliary Control Room (which is in much better shape than the ship's primary bridge), where they find tapes containing several ship's logs as well as a functioning reader. The logs describe the Republic's battle with two cloaked (but not Romulan) ships near the Vardaine system, which caused her some damage. When the Republic then encountered the Enterprise it asked for Scotty's help with repairs, but the Enterprise opened fire instead and defeated the Republic, leaving it in its current state.
Due to heavy damage to the ship's computer, Spock has to hook up his and McCoy's tricorders to the computer, allowing him to route power to the ship's shields. As soon as he does this, an Elasi pirate ship suddenly de-cloaks on the main viewscreen, apparently having waited in ambush for the Enterprise to move far enough away. The Elasi Captain demands that Kirk send information from the Republic's computers about the same terrorists that the hijacker of the Masada failed to retrieve (in episode 2, "Hijacked"). Kirk asks for more time, seeing how the Republic's computer is heavily damaged - and the Elasi agrees.
Kirk considers firing the Republic's last torpedoes at the Elasi ship, but the Fire Control System indicates a jam in the launch mechanism. Unfortunately, the torpedo bay is inaccessible due to a hull breach. Instead, Kirk and the team opt to use the transporter, which they hook up to a portable power pack found in a corridor near Main Engineering. Ensign Kije, the security officer, volunteers to transport to the weapons room, where he unjams the doors of the torpedo tube and is beamed back unharmed.
The team returns to the Auxiliary Control Room and Kirk contacts the Elasi Captain. He explains that the Republic is too damaged to transmit the information, and asks the Elasi captain to beam aboard to collect it himself. The Elasi falls for the ruse and drops his shields, whereupon Kirk fires two torpedoes at the Elasi ship, disabling its weapon systems. The Enterprise rushes back, and the Elasi cloak their ship and disappear.
Returning to the Enterprise, Kirk takes the ship to the planet Vardaine, guessing that the "fake" Enterprise would be found there. Vardaine is a Federation world, but its government does not see eye-to-eye with the Federation, and its culture respects different values from the Federation's lofty ideals - dabbling in eugenics, refusing to share technology, flaunting human rights, and rejecting a Federation inquiry into their violations. As expected, the Enterprise encounters its twin ship near the planet.
The fake-Enterprise is commanded by Dr. Ies Bredell, a man whose illegal practices had been exposed by Kirk a decade earlier when he was serving on the U.S.S. Farragut. Bredell is holding a grudge, and having created a replica of a Constitution-class vessel based on stolen blueprints, he has named it Enterprise-2 and has vowed to take his vengeance on Kirk by destroying his ship - the real Enterprise.
As battle ensues between the two identical vessels, two Elasi pirate ships de-cloak and join the fight. Despite the odds, the well-trained crew of the Enterprise manage to come out on top, destroying all three foes.
Once the battle is over, the Enterprise receives a message from Starfleet summing up their performance during the entire game (the fourth year of the Enterprise's "five-year mission to explore strange new worlds", etc.). Thanks to their stellar performance, Starfleet has decided to grant the crew some shore leave.
The story of the Enterprise's fifth year continues in Star Trek: Judgment Rites.