Aleena and Wrex first met when they were hired to assassinate the same turian, and ended up splitting the "winnings" — he got the head, she got the rest — but their friendship was tested when Wrex received a new contract: he was hired by a volus diplomat to kill someone from the volus' past who knew "too much", who turned out to be Aleena. She and Wrex joked about it, but there was still the matter of Wrex's contract.
Due to the respect of each other's skills, Wrex and Aleena agreed to battle it out. Aleena chose an old salarian space station overrun with mercenaries and pirates as their battleground, so no one who got in their way could be classed as an innocent bystander. Wrex pursued Aleena through the space station for days, until he ran out of ammunition and had to kill several mercenaries to obtain their weapons.
Finally, when all the others on the station had fled or been killed, Wrex trapped Aleena in the medical bay, while she attempted to heal her wounds. As Wrex began to break in, he realised the station's core was about to go critical and just managed to escape before the facility was reduced to vapor. There was no apparent way Aleena could have escaped, but Wrex received a cheerful message from her, simply reading "Better luck next time..."
While Shepard listens to this story, the Commander asks Wrex what he told the volus diplomat, whereupon Wrex claims he told the truth — that Aleena is still alive and is really pissed off. However, Wrex saw this as an opportunity, pointing out he was the only one who could protect the volus from Aleena now, and the diplomat hired him as a personal bodyguard immediately. This arrangement lasted until the volus died of natural causes. Wrex considers it the "easiest job I ever had."