The opening cinematic features the destruction of a rebel ship and the capture of a Jedi named Qu Rahn by the Seven Dark Jedi. Although Rahn refuses to divulge the location of the Valley of the Jedi to Jerec, the leader, Jerec uses the Force to perform a memory rip. He then knows that Morgan Katarn, whom he killed several years prior, knew of the location to the mythical Valley of the Jedi. Morgan had in his possession a map to the Valley, which was very expertly engraved into the stone tiles that made up the ceiling of his workshop.
The story's protagonists are the mercenary duo Kyle Katarn and Jan Ors. The game begins in a bar on Nar Shaddaa, where Kyle is mourning his father. He meets with the droid informant 8t88 for information on the murderer, and although he gets the information he wanted, he is also told that he doesn't factor into Jerec's plans for the rebirth of the Empire and is then held at gunpoint.
8t88 produces a unique data disk that belonged to Morgan. He tries to coerce Kyle into telling him what the data disk is, claiming he is unable to crack its code. Kyle refuses and, after successfully killing and/or scaring off the aliens holding him at gunpoint, chases 8t88 through the city, eventually catching up to him as he is boarding a shuttle and blasting his arm off. 8t88's arm, holding the disk, tumbles over the edge of the landing platform, and Kyle retrieves it. After fighting his way to the rooftops of Nar Shaddaa to be picked up by Jan, he is badly injured and spends some time recovering on a medical frigate. Rahn comes to him in a vision and informs him of Jerec and his goal. After Kyle recovers, he takes the data disk to his father's home, retrieves Rahn's lightsaber from WeeGee (the family droid), and begins fulfilling his destiny to become affiliated with the Force and stop the Seven Dark Jedi.
The entire first half of the game is a giant rat race. Kyle's main focus is chasing 8t88 from place to place, who has since uploaded the map into his memory and delivered it to Jerec. 8t88 relinquishes the map to Kyle, but it is promptly destroyed by one of the Dark Jedi. After chasing 8t88 a bit more, Kyle sneaks onto 8t88's cargo freighter, the Sulon Star, and eventually catches up to him to find that he has been decommissioned and decapitated. After dispatching the two Dark Jedi that shut down 8t88, Kyle grabs 8t88's head and works his way back out of the cargo freighter. Jan picks him up and they plug 8t88's head into Weegee so the map can be projected. Once the location of Ruusan (the location of the Valley) is confirmed, Kyle and Jan head over.
The second half of the game is more directed towards Kyle's focused efforts to stop Jerec from accessing the ancient Jedi burial grounds found deeper within the planet, which hold all of the collective force power of thousands of Jedi who were trapped there. It is spent at the Valley of the Jedi as Kyle meanders through the Imperial facilities that have been established. During this process, Jerec's goons find and capture Jan and present her to Kyle to be either killed or spared. Doing one or the other decides the path Kyle takes. Either way, Jerec grows weary of Kyle's persistence and forces him back onto the cargo freighter with a tremendous burst of Force power. The ship, which is knocked offline, begins plummeting to the planet's surface. Kyle escapes and finds that the ship's impact has stripped away much of the outer infrastructure, allowing him to venture deeper underneath the planet's surface and eventually to the drilling site that has unearthed the burial ground. When he reaches the core of the burial ground, the final showdown with Jerec begins.