The game's arenas are similar to those in Mortal Kombat: Deadly Alliance, but include new features such as unique weapons which players can use, and instant-death traps which immediately kill a fighter who falls into them. The game also introduces the "Combo Breaker", a system which allows players to interrupt combos up to three times per match. In contrast to Deadly Alliance, in which characters had only one Fatality, the Deception characters have two Fatalities and a hara-kiri suicide move. The latter is used when the phrase "Finish Him/Her" is shown on the screen and the player is about to lose.
In the final events of Mortal Kombat: Deadly Alliance, Raiden's warriors, who were meant to protect the six realms, are killed by the Deadly Alliance (Shang Tsung and Quan Chi), who attempted to conquer the realms. With Raiden defeated, the Deadly Alliance dissolves as the two sorcerers turn on each other for Shinnok's amulet. When Quan Chi wins, the Dragon King Onaga, the former emperor of the realm of Outworld, appears to regain his power. Raiden awakes and then unleashes all his powers in a colossal explosion that, apart from destroying both members of the Deadly Alliance, the surrounding palace and himself, has little effect on Onaga.
Onaga now seeks to use six artifacts called Kamidogu, which are able to destroy the realms. Those fighters who survive the battle against the Deadly Alliance now stand against Onaga and his supporters. The latter include the forces of Edenia, now led by Mileena in the titular theme of deception as she masquerades as her sister, Princess Kitana. Other enemies include the former defenders from the realms, who were resurrected by Onaga and are under his control.
In the story explored in Konquest mode, a young man named Shujinko is deceived into spending his entire life collecting the Kamidogu for Onaga, who uses the guise of an emissary of the Elder Gods, the beings who created the realms, named Damashi. Onaga reveals his identity and intentions after Shujinko has gathered all the Kamidogu. Shujinko, led to believe he was working for the greater good, decides to continue training to defeat Onaga