Con SNK ya metida en plena decadencia y con un sistema que tenía ya nueve años, se decide volver a la carga con un nuevo King of Fighters, con una nueva trama, un nuevo sistema de juego y gran cantidad de nuevos personajes. Graficamente el juego ha mejorado poco respecto a las versiones anteriores, aunque podemos ver una mejora bastante importante en los escenarios y en las imagenes de final de combate, que ahora ya són decentes y acordes con la época en la que corremos. El número de sprites sigue siendo más o menos igual, aunque en personajes como K' podemos observar que tienen una gran cantidad. Eso sí, nunca al nivel de los últimos juegos como Street Fighter 3, Guilty Gear X o el tambien juego de SNK, Fatal Fury: Mark of the Wolves.

La banda sonora del juego quizá haya bajado un poco el nivel, pero es poco apreciable, sigue siendo excelente, con temazos como Tears, de Kyo o The Way to Rebirth del equipo coreano. Sigue siendo la banda sonora de un King of Fighters, lo que la hace realmente buena.

Y por último el sistema de juego, que es en lo que trae más novedades este King of Fighters 99. Además de los nuevos movimientos incorporados a cada personaje como en cada capítulo, ahora también se incorpora un sistema de strikers al más puro estilo Marvel vs Capcom. En los equipos de 3 tendremos que elegir a un 4º personaje que hará las veces de striker, apareciendo en pantalla, dandole unas cuantas tortas al contrincante, y marchandose otra vez. Tendremos una barra debajo que nos indicará los strikers que nos quedan por poder utilitzar. Y el resto de cambios són los de siempre, ajustes de jugabilidad, las tipicas opciones de single match, team survival, single survival...vamos, un King of Fighters.

Tras la batalla de Orochi, Kyo e Iori quedaron exhaustos tendidos en el suelo. Entonces una misteriosa figura que había estado siguiendo las evoluciones del torneo desde hacía tiempo apareció en la escena y se llevó a Kyo. Tras hacerle varias pruebas en su laboratorio, Kyo se escapó de la organización que le tenía atrapado, pero esa organización ya tenía lo que quería...

Año 1999, las invitaciones para un nuevo King of Fighters són enviadas a los luchadores por alguien desconocido. Esta vez se envían 4 invitaciones por equipo en vez de 3. Benimaru y Shingo forman equipo con dos misteriosos nuevos luchadores, K' y Maxima. El resto de los equipos, el Garou Team con Mai como nueva incorporación, RyukoNoKen Team con la vuelta de Takuma, el Ikari Team, con una nueva jovencita llamada Whip, Psycho Soldier Team, con un chavalillo que se llama Bao, el Gals Team tambien con la incorporación de XiangFei, de Fatal Fury Real Bout 2, y el Korea Team, como no, con un nuevo personaje, Jhun Foon. Y por último se incorporan al torneo ¡Dos Kyo iguales! Estos 2 Kyo no són otra cosa que dos clones del original...realmente misterioso. Tambien estarán rondando por el torneo Kyo que quiere saber quien fué el que le secuestro, e Iori, que sigue buscando a Kyo...pero ahora ya sólo le quiere para pelear contra el mejor tras él.

Poco a poco el torneo va progresando, y con ello se va descubriendo también su trama. El grupo de inteligencia que comanda Heidern está siguiendo de cerca a K' y a Maxima, temiendo lo que puedan hacer, y de paso están controlando al misterioso organizador del torneo, un grupo terrorista internacional conocido como "El Cartel de Nests".

El Hero Team, formado por K', Maxima, Benimaru y Shingo llega a las finales. Allí les aguarda un misteriosos guerrero. Mientras, en el cuartel de Heidern, se descubre por comunicación vía satélite el plan urgado por el cartel de Nests. El cartel ha preparado un ejército de clones de Kyo con el que pretende conquistar el mundo, sólo falta activarlos, para ello se necesita mucho poder.

Tras una lucha en que el Hero Team vence sin muchas dificultades al guerrero misterioso que les esperaba, éste se revela. Su nombre es Krizalid, y está intentando mediante sensores instalados en su cuerpo recoger poder de los luchadores del torneo para despertar a los clones, tarea que ya casi ha conseguido. Entonces Krizalid le revela a K' que él es un clon suyo (aunque al final esto resultará ser al revés, siendo Krizalid un clon de K' a la orden de los Nests), pero K' no le cree y se dispone a atacarle. Krizalid es derrotado por el Hero Team. Todos los clones han sido desactivados y el plan del cartel es al fin . Al haber fracasado en su misión "0alguien" destruye la base, sacrificando así a Krizalid y a todos los que habían dentro. Mientras la base se está derrumbando Krizalid intenta volver a luchar, pero entonces aparece Kyo y lo acaba de noquear, él había estado siguiendo el torneo y quería saber quienes eran y por que le capturaron. Los hombres de Heidern llegan al lugar y se encuentran con el cuerpo de Krizalid, y a K' y Maxima, a los que Heidern persigue por ser terroristas. K' y Maxima huyen. Entonces un joven pelirrojo aparece en escena, quiere pelear con Kyo a pesar de que la base se está desmoronando. Iori y Kyo empiezan entonces su combate...