In the 2360s, Lieutenant Leijten served on the USS Victory. It was during this time that she became good friends with Geordi La Forge while he served there, calling him her "little brother" and would occasionally give him advice with women. They would later remark that they made a good team. Leijten also had a relationship with Paul Bogrow. Initially, she thought he was "full of himself" and would annoy her, but, for a time, she thought she might have been wrong and had almost married him.
In 2362, the Victory received word that the staff of a Starfleet outpost on the planet Tarchannen III had disappeared. Leijten commanded an away team to investigate. She brought Lieutenant Geordi La Forge and ensigns Anthony Brevelle, Paul Hickman and Emilita Mendez. They found no sign of struggle, just the absence of the outpost staff and some tattered clothing. Without any more evidence, they abandoned the outpost, however, unbeknownst to them, they were all exposed to an alien retro-DNA that started to turned them into alien lifeforms.
In 2367, Leijten got word that three of her former crewmates had disappeared. After she heard from a Federation supply ship that Hickman's stolen shuttlecraft was heading for Tarchannen III. When the pattern was recognized from her away mission five years ago, the USS Enterprise-D was contacted to investigate. She boarded and informed senior staff, including La Forge, of the away team's mission and reviewed the sensor log. When they landed on the planet to investigate, Lieutenant Commander Leijten started to act strangely, refusing to leave. La Forge beamed her to sickbay where Dr. Crusher found that she was undergoing chemical changes. Later, she was covered with dark blotches and her hands were mutating. Alien DNA had started to change Leijten into an alien lifeform. However, Dr. Crusher performed a genetic treatment to reverse the effects. Commander Leijten then helped in the rescue of La Forge, who by that time was further along in his transformation and had returned to Tarchannen III. She talked him into coming back with her. (TNG: "Identity Crisis")