Так как, согласно сюжету, практически все известные бойцы погибли в сражении, то игрокам предстояло освоить множество новых.
Ашра – Демон, который явился из той же Преисподней, из которой в свое время сбежал Шиннок. Обладает мечом Крисс, которым валит других демонов направо и налево, надеясь, что таким образом очистит свою черную душу.
Хотару – Воин Порядка, изменивший своим принципам и примкнувший в Онаге.
Дайру – В недалеком прошлом был подчиненным Хотару, но теперь стал наемным убийцей, чья задача убить своего бывшего босса.
Хавик – Клерик Хаоса, спасший Кабала и сам вставший на сторону сопротивления против Онаги.
Кира – Раньше занималась торговлей оружием, а теперь принята Кабалом в «Черный Дракон».
Кобра – Кикбоксер, выгнанный из спорта за жестокое обращение с противниками, так же принят Кабалом в «Черный Дракон».
Судьзинко – Постаревший воин, которого Онага обманом заставил собрать Камидогу и воскресить себя самого.
Онага – Король Дракон и действующий император Внешнего Мира.



Все же некоторым полюбившимся всем бойцам, из прошлых частей, удалось выжить и занять свое место в новом сюжете.
Кабал – Был спасен клериком хаоса Хавиком, и теперь стал во главе возрожденного клана «Черного Дракона».
Барака – Командующий армией Таркатанов, которая, совместно с почившим Смертельным Альянсом, убила прибывших воинов земли.
Бо Рай Чо – Тот самый легендарный учитель из Внешнего Мира, Судьзинко один из его учеников.
Лю Кенг – Да, бывший многократный чемпион Смертельной Битвы вернулся, правда, в необычном для себя амплуа, он воскрешенный зомби.
Милина – После гибели Китаны, этому клону наконец-то удалось занять место принцессы и встать на сторону Короля Дракона, чтобы уничтожить Эдению.
Ермак – Некогда член клана «Черный Дракон», теперь воскресший в виде убиенных душ и помогающий зомби Лю Кенгу в его миссии.
Кеньши – Слепой боец с мечом, который когда-то был обманут Куан Чи и теперь спасен Саб-Зиро.
Ночной волк – Индеец, который решил по-своему уничтожить Онагу. Для этого он взял на себя обязательство пожирателя грехов, чтобы пройти через врата Преисподней и нанести удар оттуда.
Нуб-Смоук – Необычный альянс между Нуб-Сайботом, некогда бывшим старшим Саб-Сиро, убитым на первом турнире Скорпионом, и ниндзя-киборгом Смоуком. Нуб-Сайбот хочет создать собственную армию демонов-киборгов, а Смоук ему необходим, как прообраз.
Рейден – Все-таки здорово быть бессмертным, он воскрес на Земле и снова вступил в борьбу с Онагой.
Скорпион – Свежеиспеченный чемпион от Старших Богов, которого послали покончить с Онагой.
Саб-Заро – Запертый во Внешнем Мире, вместе со спасенным Кеньши, лидер клана Лин Куэй отчаянно ищет выход.
Таня – Та самая предательница Эдении, теперь работает на Онагу и ищет для него информацию о Камидогу.
В версии для GameCube, PSP и PS2 в игре появляется Шао Кан и воскрешенный им Горо, вместе с ним, поверженный император ищет способ вернуть трон.



Помимо большого количества новых бойцов, появились интересные режимы игры.
Конквест – Приключение с элементами РПГ, в котором рассказывается история обманутого Судьзинко, начиная со времени его обучения у Бо Рай Чо. После того, как Конквест будет пройден, Судьзинко становится играбельным персонажем, со своей сюжетной линией.
Крипт – Режим, который стал меньше чем в предыдущей части, но разнообразнее. Проходя его и сражаясь с различными персонажами, можно было открыть до 12 различных бойцов, со своей историей и сюжетом.


Chess Kombat – В чем-то напоминаете классические шахматы, но все фигуры представлены в виде бойцов, а чтобы побить вражескую фигуру, необходимо победить бойца на этой клетке.