Tenmei joined Starfleet in 2369 at roughly the same time her mother went missing in action during a confrontation with the Borg during a Starfleet Intelligence operation commanded by her father. Tenmei's relationship with her father was strained for several years. The two achieved something of a reconciliation after Vaughn transferred to station Deep Space 9. ('Star Trek: Deep Space Nine' novels: Avatar, Lesser Evil)
Tenmei had been assigned to DS9 as early as 2375 when she overheard a debate between Julian Bashir and Miles O'Brien in Quark's about the truth of the legend of Davey Crockett, which Lieutenant Commander Worf resolved. (Star Trek: War Aftermath Episode 1: The True Way, DS9: "Once More Unto the Breach") She recalled that debate when Bashir and Raul Fitzpatrick stepped onto the bridge of the USS Defiant debating an issue relating to a different holosuite program.
Tenmei was none too pleased to be assigned to a mission to rescue hostages of the True Way on Cardassia Prime. Ezri Dax attempted to boost her enthusiasm during the ship's pre-flight preparation. Tenmei was left in command when Vaughn and Dax led missions to rescue the hostages and prevent the assassination of Alon Ghemor. Despite the rocky relationship with her father, she did not relish the possibility of abandoning him if he failed to return in twelve hours. Fortunately, she did not have to carry out that order. (Star Trek: War Aftermath Episode 1: The True Way)