The Mission to Nar Shaddaa involved Kyle Katarn, who had recently regained his abilities with the Force. Driven by a personal vendetta against the Empire Reborn, whom he blamed for the supposed demise of Jan Ors, his objective was to locate Reelo Baruk. Baruk was believed to possess information about the Dark Jedi named Desann, information that would allow Katarn to pursue Desann.
Katarn made his way to a bar, where all of his weapons were confiscated, with the exception of his lightsaber. He proceeded to move through the bar, attempting to extract information from the patrons. However, he was met with nothing but hostility. Eventually, he approached the bartender, a Chiss with a peculiar way of speaking. Just as it seemed Katarn was making progress with his inquiries, the bartender double-crossed him, sealing the bar and signaling the patrons—all of whom appeared to be thugs working for Baruk—to attack.
Katarn easily overcame them by using his newly restored Force powers, and once again confronted the bartender. The terrified Chiss revealed to Katarn that Baruk's hideout could be found by following the garbage haulers in the upper levels. Katarn exited the bar and made his way to the higher levels of the street. While ascending, he faced numerous thugs employed by Baruk, all of whom tried to impede his progress. Ultimately, he managed to infiltrate Baruk's hideout by concealing himself within one of the city's numerous garbage collection repulsor sleds.
Inside the hideout, which appeared on the surface to be a simple garbage processing facility, Katarn had to navigate a variety of dangers, including a smelter and a vast storage area. He encountered a security door that provided access to Baruk's hideout, but it required a password for entry. After further exploration, he eventually encountered Lando Calrissian, who was being held prisoner by Baruk's thugs. Katarn inquired with Calrissian about any methods to disable the force field surrounding his prison cell. Calrissian informed him that it could only be deactivated from Baruk's command center. Fortunately, Calrissian knew the password to its security door. The code was ruby bliels, a drink that the Chiss bartender had ironically offered him earlier at the bar. Using the code, he entered Baruk's command center, where he found the Rodian. Baruk was not incompetent; he had set a trap for the Jedi, consisting of ceiling-mounted laser cannons, followed by a large group of thugs. Katarn survived the ambush, but Baruk managed to escape through a tunnel located at the back of his office.
Katarn then rescued Calrissian, using a control on Baruk's desk. Calrissian offered Katarn a means of escape from Nar Shaddaa aboard his ship, the Lady Luck. The ship was heavily guarded by Baruk's thugs and also needed refueling. Katarn took care of this, and also opened the doors above the ship to allow it to leave, while Calrissian inspected the on-board systems.
Before they could depart from the Vertical City, Baruk and some of his elite thugs launched an attack. Katarn assumed control of a laser cannon situated on the Lady Luck's ventral surface and eliminated Baruk and his thugs. Having successfully escaped, Katarn agreed to accompany Calrissian to Cloud City, which was under the control of the Empire Reborn, hoping to uncover more information regarding Desann's location.
This mission is featured in the video game Star Wars: Jedi Knight II: Jedi Outcast, which was released in 2002.