No advento de um novo torneio King of Fighters, novos rostos são convidados , enquanto velhos conhecidos retornam , como Eiji Kisaragi (que faz seu retorno aguardado desde sua última aparição em The King of Fighters 95 ) , que cria o time Anti- Kyokugen Ryu junto com Kasumi Todoh e Malin.
Eles uniram forças, pois todos possuiam assuntos inacabos com o time do karate, o clã Kisaragi é rival da familia Sakasaka a muito tempo, Kasumi depois de perder uma luta para Ryo, o marcou como seu rival eterno, e Malin tinha um grande recentimento por Yuri ter chamado seu estilo de luta de "covarde" no torneio passado.
Ash, recruta Shen Woo novamente, pois o mesmo queria uma chance a mais de lutar contra adversarios mais poderosos, e Oswald.
Oswald, um irlandês especialista no uso de suas cartas para a batalha , se junta para encontrar o paradeiro de uma nova e poderosa droga . Um homem desconhecido disse a ele que se derrotasse seu inimigo Shen Woo, lhe diria como encontra-la. E isso era perfeito para Ash, pois o conflito interno em seu time lhe ajudaria em seu plano.
Elisabeth Blanctorche , uma jovem francesa que está familiarizada com Ash, cria o time rival(Rivals Team) junto com Benimaru Nikaido e Duo Lon para investigar as verdadeiras intenções de Ash.
Elisabeth, primeiramente convida, Duo Lon e Benimaru para sua mansão, lá ela explica que foi criada junto a Ash, ele seria como seu irmão mais novo, também fala que sabe sobre a traição de Ron ao clã Hizuku, então eles concordam em fazer time, para descobrir o que Ash tramava e captura-lo de uma vez.
Duck King, um vetereno lutador bem conhecido em South Town, se junta a Terry Bogard e Kim Kaphwan na equipe de Fatal Fury, como Joe Higashi decidiu se concentrar mais em seu treinamento e Mai Shiranui se recusou a entrar no time, pois Andy estava desaparecido e Terry não sabia o paradeiro dele.
Terry ficou sem parceiros de equipe, e sempre querendo lutar contrar adversarios mais poderosos decidiu convidar velhos conhecidos. Duck King era um lutador diferenciado, que usava o Breakdance como estilo de luta, e Kim. Kim de inicio recusou o convite, mas foi convencido por Chang e Choi, que diziam terem sido "reabilitados", por isso ele não precisava se preocupar mais com os mesmos.
Depois do treinamento especial de um ano com Chin, Sie Kensou retorna ao time dos soldados psíquicos(Psycho Soldier Team), junto a Athena Asamiya e recém-chegada Momoko , uma alegre capoeirista.
Todos queriam ver o quão poderoso Kensou estava, já que além de recuperar seus poderes, teria aprendido sobre o poder do dragão, Momoko era uma grande fã de Athena, e a mesma quando descobriu que ela possuia poderes psiquicos, a convidou pessoalmente para o time, Kensou não aceitou de inicio, mas depois de um surra que Athena da nele, ele fica calado. Com a entrada de Momoko e a recuperação dos poderes de Kensou a equipe passou a se chamar, Neo Psycho Soldier team.
Uma nova equipe é formada por Blue Mary , com Vanessa e Ramon .
Blue Mary recebe a missão de investigar sobre o selo de Orochi que havia rompido, quando se depara com seus parceiros, Vanessa e Ramon. Vanessa diz que ja trabalhou junto com o falecido grande amor de Mary, Butch. E Ramon estava atuando como agente apenas para continuar perto de Vanessa. Juntos formaram o Agent Team
E mais uma nova equipe aparece chamada de Mark of the Wolves Team.
A pirata Bonne Jenet, pensando no dinheiro do prêmio convida Gato e Tizoc a entrarem na sua equipe. Gato entra, pois B. Jenet diz ter informações sobre o paradeiro de seu pai, já Tizoc entra apenas pelo gosto e espirito de luta.
Devido a um medo de se descontrolar e atacar seus parceiros como o ocorrido no toneio de 2003 Leona se recusa a participar.
Então Whip decide juntar-se novamente com seus antigos companheiros e ocupar seu lugar no Ikari Team.
K' mais uma vez não tinha interesse em particpar do campeonato.
Só que ainda estava com as ultimas palavras de Mukai na cabeça, com isso, e mais o desejo de enfrentar Kyo Kusanagi, pegou seu melhor amigo Maxima e a tambem ex-NESTS, Kula Diamond, e entra na competição com o time K'(K' Team).
Uma grande mudança nos times, foi a presença de King no time Art of Fighting.
Robert não pode participar do torneio, já que a empresa de seu pai teve um grande problema, que precisava da ajuda dele para resolvê-lo. King aceita entrar na equipe sem problemas. Muitos rumores dizem que ela tem uma grande queda por Ryo, e ainda assim, o ajuda em um encontro com outra garota.
E desta vez, Kyo e Iori não poderiam entrar como membros especiais, então decidiram formar um time.
Como Chizuru havia perdido os poderes, decidiram convidar Shingo para entrar no time, e esse claro, aceito de primeira. Eles queriam derrotar Ash para recuperar os poderes de Chizuru, e assim fechar mais uma vez o selo de Orochi.
Muitos lutadores especiais entraram neste torneio, a grande maioria deles apenas queria testar suas forças, com excessão de Adel(Adelheid), que secretamente estava coperando com Heidern, para descobrir informações sobre Ash, "Those from the Past" e o selo de Orochi.
Os guerreiros espeiciais são:
Sho Hayate, Jyazu, Silber e Gai Tendo, todos convidados, por serem conhecidos como grandes guerreiros.
Rose e Adel são os anfitriões deste torneio, no torneio passado Adel teve sua derrota, e ao encontrar-se com o Ikari team, argumentou com Heidern que apenas estava seguindo os passos do seu pai, e depois de muita conversa concordam em cooperar.
No fim a equipe de Ash perde, e enquanto caminha com seu time, decide começar à por seu plano em pratica, joga Olwald contra Shen, e vai embora, enquanto eles começam uma batalha de vida ou morte.
Ele ja tinha planejado isso desde o inicio do torneio, e como Oswald ja havia entrado com esse proposito, Ash não precisou de muito esforço.
Antes disso o time Kyo&Iori vence o time K', e logo após isso em meio aos destroços causados pela violenta luta, um rosto desconhecido aparece.
Um homem androgeno (com aparecencia feminina). Shion era seu nome, revela que faz parte dos "Those from the Past", e estava ali por onders de seu mestre, para reviver o poder orochi de uma vez.
Depois de uma dificil luta Kyo, Shingo e Iori saem vitoriasos, Shion reluta pela derrota, mas quando ele menos espera é sugado para outra dimensão por uma mão azulada.
Quem se revela é Magaki, mestre de Shion que o utiliza como âncora para chegar a esse mundo. Mesmo sendo membro dos "Those from the Past ", Magaki não aceita a ideia de Mukai de observar os humanos de longe, e decide por si só reviver totalmente o poder de Orochi e usa-lo para seus fins.
Magaki foi o membro do clã que ficou com o poder de Orochi, na quebra do selo, no torneio passado, agora ele manifesta esse poder e parte para destruir as duas peças que faltam, Kyo e Iori.
Despois de muita luta, o time ja estava cansado, quase sem forças, por sua vez Magaki tambem, ele começa a perceber que o poder de Orochi esta indo embora. Percebe que os lutadores eram mais poderosos do que ele imaginava e decide voltar para sua dimenção. Antes disso ele liberta o Motim de sangue (Riot of the Blood) em Iori, abre a fenda e não para de
gargalhar.
A unica coisa que ele não contava, era que Shion estava vivo, e o ataca de dentro do portal com sua lança, tirando sua vida de uma vez por todas.
Ninguem nunca saberá os verdadeiros propositos de Magaki. E mesmo com Magaki morto e Shion preso em outra dimenção, os guerreiros não poderiam descansar, pois Iori estava descontrolado, graças ao motim de sangue.
A luta foi intensa, Kyo estava caído desacordado e Shingo quase morto, ele via Iori indo em direção a Kyo sem poder fazer nada, não tinha mais força alguma. E nesse exato momento Ash aparece, aproveitando-se que Iori estava descontrolado, rouba sua relíquia, assim tirando seus poderes, Shingo apenas assiste a cena, desolado por não poder ajudar em nada.
Quando Ash estava prestes a ir embora o time de rivais chega. E Elisabeth logo pergunta o porquê Ash abandonou a mansão, Ash apenas diz que tinha seus proprios planos.
Enquanto isso o time observa Kyo, Shingo e Iori em estado deploravel, e Elisabeth decide que vai parar Ash.
Mais o mesmo da uma demostração de poder, usando as chamas purpuras do clã Yagami e desaparece.
Após isso Elisabeth promete a si mesma, que vai acabar com esse tal plano de Ash e leva-lo para casa.
No dia seguinte, o time de agentes especiais vai ao porta aviões, onde Heidern esta parabenizando seu pelotão por completar a missão.
Heidern esta parabenizando o seu pelotão, pois eles conseguiram trazer o corpo de Magaki, para que pudesse ser estudado, com isso eles teriam maiores informações sobre o grupo "Those from the Past".
K', Kula e Maxima estão na comemoração, observando tudo, ja que Whip é irmã de K' e, praticamente uma tia para Kula.
Tudo parecia ir bem, até que Kula sente uma presença estranha, e no mesmo momento ocorre uma explosão em um dos porta aviões.
E rapidamente mais dois membros da "Those from the Past" aparecem no barco, dizendo que vão levar o corpo de Magaki, um deles retira o tapa olho de Heidern. Os mesmos confirmam que aquilo era apenas o inicio e que o pior estaria por vir, após isso eles desaparecem, e Heidern da a ordem para que sejam capturados.
E esse é o fim de mais um torneio, o selo de Orochi esta destruido, Iori havia perdido seus poderes, Ash promete que ira roubar o poder de Kyo, ninguem sabe o verdadeiro plano dos "Those from the Past", a unica certeza era que o pavor estava na mente dos homens mais uma vez.