Kei and Yuri were originally junior auxiliary agents in the Worlds Works and Welfare Agency (W.W.W.A. or 3WA for short) when the two were paired together under the codename "Lovely Angels." Kei was coming off her fourth probation for something she had done, and Yuri's dating exploits were common knowledge, not to mention the two had an instant dislike for each other when they met.
Kei and Yuri were not the first to receive the codename Lovely Angels. Years before, during the Gamorian Riots, two other women, Iris and Molly, had been given the designation Lovely Angels. Molly was killed in action, and her partner Iris, who had lost her right arm trying to save Molly, became bitter about the lack of response from the 3WA and vanished, later becoming the notorious assassin known as "Lady Flair."
At first, Kei and Yuri refused to work with each other, and Kei even resigned from the 3WA. However, when the "Siren" crisis erupted, Kei returned. This was decidedly a good thing, as Yuri's ditsy new partner, Lily, had abruptly quit just as the response to the crisis started, and Kei's return came just in time, as Yuri was about to be killed by Waldess.
Afterwards, the two continued to work together, although they earned their nickname, "the Dirty Pair" because of all the collateral damage the two (unintentionally) cause in the completion of their cases. And even though the two now get along with one another, they continue to bicker and complain to each other.