Yhteenveto
Rugal Bernstein on uskomattoman rikas ja pahamaineinen aseiden ja huumeiden salakuljettaja sekä erittäin taitava ja armoton taistelija. Kyllästyttyään kilpailun puutteeseen Rugal päättää järjestää uuden King of Fighters -turnauksen. Rugal lähettää sihteerinsä kahdeksaan eri kohteeseen ympäri maailmaa kutsumaan taistelijoita hänen uuteen turnaukseensa. Toisin kuin aiemmissa Fatal Fury -sarjan KOF-turnauksissa, uusi King of Fighters on joukkueturnaus, jossa on mukana kahdeksan kolmen hengen joukkuetta, joista jokainen edustaa eri kansallisuutta. Useimmat hahmot ovat peräisin muista SNK-peleistä, kuten Italian joukkue, joka koostuu kolmesta alkuperäisen Fatal Furyn sankarista: Terry Bogard, Andy Bogard ja Joe Higashi. Art of Fighting -pelistä tutut kaksi sankaria (Ryo Sakazaki ja Robert Garcia) ovat mukana yhdessä heidän mentorinsa ja Ryon isän (Takuma Sakazaki) kanssa muodostaen Meksikon joukkueen. Korean joukkueessa on Fatal Fury 2 -pelistä tuttu Kim Kaphwan kahden vangin, Chang Koehanin ja Choi Boungen kanssa, joita hän yrittää kuntouttaa. Englannin joukkue on sekoitus naispuolisia taistelijoita Fatal Fury 2:sta (Mai Shiranui) ja Art of Fighting -sarjasta (Yuri Sakazaki, King). Psycho Soldier -pelin kaksi sankaria (Athena Asamiya ja Sie Kensou) muodostavat Kiinan joukkueen mentorinsa Chin Gentsain kanssa. Samoin Brasilian joukkue koostuu Ikari Warriors -pelin sankareista (Ralf ja Clark) sekä heidän komentajastaan Heidernistä. Lisäksi pelissä on kaksi kokonaan alkuperäisistä hahmoista koostuvaa joukkuetta: Japanin joukkue, jossa ovat Kyo Kusanagi, Benimaru Nikaido ja Goro Daimon, sekä Yhdysvaltojen joukkue, jossa ovat Heavy D!, Lucky Glauber ja Brian Battler.