The opening cinematic features the destruction of a rebel ship and the capture of a Jedi named Qu Rahn by the Seven Dark Jedi. Upon refusal to divulge the location of the Valley of the Jedi to Jerec, the leader, Rahn is killed. However, Jerec knows that Morgan Katarn, Kyle Katarn's father, possesses the location of the Valley, and thus Morgan becomes his next target.
The story's protagonists are the mercenary duo Kyle Katarn and Jan Ors. The game begins in the wake of Morgan's death; he was killed by Jerec in his search for the location of the 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 family droid, Weegee, was given Rahn's lightsaber for safekeeping until Kyle returned to claim it, and would only awaken and eject the lightsaber after playing a message Morgan left for Kyle on a unique data disk. This disk, however, was found by the Seven Dark Jedi when they killed Morgan, and is in the possession of 8t88, the droid who is sent to carry out Jerec's handiwork and lure Kyle into an eventual trap so that he can be killed as well.
Kyle's journey begins in a bar on Nar Shaddaa. He is approached by 8t88, who tries to coerce Kyle into telling him what the data disk is, claiming he is unable to crack its code. Kyle refuses and chases him 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. He takes it to his father's home, retrieves Rahn's lightsaber, 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 chases 8t88 from place to place, encountering a Dark Jedi on the way, and eventually catches up to him to find that he has been decommissioned. 8t88's function was to upload the map of the Valley to his memory so that Jerec could locate it, and to trap Kyle with Dark Jedi who intend to kill him so that he will not find the Valley.
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 every Jedi buried 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 Ors and present her to Kyle to be either killed or spared. Doing one or the other decides the path Kyle takes. His goal on the light side is to stop the Seven Dark Jedi so that the burial ground's power can remain untouched, while his goal on the dark side is to stop Jerec so that he himself can harness the force power and become the new emperor.