When Kitana was freed from Onaga's yoke, Mileena retreated before it was too late; she wouldn't let "her" people the time to learn the truth. She retreated and found Baraka who blamed her for some treachery... as the cunning and manipulative bitch she is, she convinced him that it was her undoing. Baraka gave her a chance and he agreed for her to assist him in the leading of the Tarkatan army. They made a hasty retreat so their armies could be safe, fearing that Onaga would be defeated... they learned that the Shaolin monk Liu Kang was back somehow. Mileena decided that it was finally time for Kitana to die. She wouldn't launch herself into Kombat this time... she needed a plan...

Mileena searched for powerful allies to aid her... Kahn was dead and Shang Tsung was nowhere in sight. She had learned that he was killed... or was he. She sent Tarkatans scouts into Outworld... Shang Tsung, however, had lost his souls, and he was old and depowered, so he went to Earthrealm to hide. His double agents learned of Mileena's intentions, and they told Tsung about it. The sorceror decided to meet her. He traveled to Outworld where Mileena was. Upon seeing him, she was shocked and enchanted. She told him she would give him her services again, at one condition....

Shang Tsung agreed, and so, to show some faith, she gave him two of Baraka's best armies. What Shang Tsung did and where he went afterwards is still unknown. The pact was that in exchange for Mileena's militias, he would give her a flawless face, so she could trick the queen of Edenia. Shang Tsung simply removed everything that was Tarkata in her self... but what they didn't know, is that by removing her Tarkatan half, she would be changed forever....

Mileena felt different, of course she was no longer a monster; she looked exactly like Kitana, but still, there was something different about her. She asked her spies to tell Tsung that they should meet at the Edenian Palace. A month later, she arrived, dressed in blue, at Sindel's Throne. Sindel was absent, but she found Jade. Upon seeing her, she said that the sorceror Shang Tsung was planning an attack, so Jade, as Kitana's general, regrouped the Edenian armies, and planned an ambush for the sorceror. Mileena, still posing as Kitana, went outside, and met with Tsung. She told him to go alone because she sent Edenia's army far away from the Palace... she was lying to the sorceror...

When she was entering the palace with Shang Tsung, Kitana, Jade and her army were waiting for them. Jade and Kitana were shocked... Mileena was unveiled and she looked exactly like Kitana... In front of everyone's eyes, she murdered Shang Tsung by impaling him in the head with her sai. He fainted and died in front of everyone... Mileena spoke before everyone, and for the first time in her life; she told the truth. By removing her Tarkatan blood, the sorceror also removed evil within her. So to prove her good intentions, she felt she had to trick everyone again and give the greatest gift Kitana could have received: to kill her murderer. Shnag Tsung, when allied with Quan Chi, was responsible for Kitana's death. So Mileena's plan was to bring justice. She then told of her plan with the sorceror and finally said: "Kitana, there was this evil inside of me, from which I am freed now... I am like you. I am you in a way, but with a different story. You turned to light a long time ago... but I couldn't until now.... I gave you the death of Shang Tsung. Will you accept me now ?....." Sindel arrived at this precise instant, and Kitana and Jade were still shocked and amazed. Jade thought she could trust Mileena, but Kitana didn't. Jade told her only to speak of this with the Edenian council and with the queen. Kitana, knowing Jade was trustworthy, accepted. Until then, Mileena would be confined to stay in prison...

Baraka, not knowing the latest events, thought she had been captured, and came to free her... She was still the clever bitch she always was, but now, her intentions were good. So she accepted to leave with him... Outside, she told him she wanted to get her revenge on Kitana once and for all, so they climbed the Palace and went in Kitana's sleeproom. Kitana was alone, and she was thinking of the decision she would have to take. They shown and yelled at her, surprised, the princess drew her steel fans and thought: "She always was a traitor..." While Baraka was going on rampage to kill the princess, Mileena backstabbed him, and finished him. ...Fatality... . Kitana wouldn't believe what she saw...

Two days later, Princess Kitana took herself the decision... Mileena would stay... she had proven herself by having killed her only love, and her most powerful ally. Mileena was finally a hero, and she had done a lot to prove it. She was worthy to be a princess of Edenia.

Mileena was finally close to Kitana... she tricked everyone this time.... everyone.... even the princess herself. The opportunity to exact her revenge was ahead of her...