Con Kyo desaparecido, sus compañeros Shingo Yabuki y Benimaru Nikaido se juntaron con dos misteriosos luchadores, K' y Maxima; Mai Shiranui finalmente es aceptada en el Equipo Fatal Fury después de seis torneos; Yuri Sakazaki, trabajando con su hermano Ryo Sakazaki y el amigo de la familia Robert Garcia, es aceptada por su padre Takuma Sakazaki en el Equipo Art of Fighting, que por primera vez cuenta con todos los Sakazaki como integrantes; King, por su parte, se vio forzada a armar un nuevo equipo femenino, reintroduciendo a Kasumi Tōdō (procedente de la saga Art Of Fighting), la cual fue vista por última vez en The King of Fighters '96, juntamente con Li Xiangfei (de Real Bout Fatal Fury 2) y Blue Mary, la cual abandona el Equipo Outlaw después de descubrir que había sido engañada por Geese Howard (el Equipo Outlaw no se presenta a este torneo); en el Equipo Psycho Soldier se introduce un nuevo personaje, Bao, un muchacho de carácter tímido pero con unos poderes psíquicos latentes abrumadores; en el Equipo Ikari Warriors se presenta a Whip, una joven que padece amnesia pero que se une al torneo por instrucción de Heidern; por último, en el Equipo Korea se introduce a Jhun Hoon, un maestro del taekwondo que comparte una relación de amistad-rivalidad con Kim Kaphwan.

El Equipo Hero integrado por K', Maxima, Benimaru y Shingo llega a la final del torneo, que tiene lugar en el subsuelo, cerca de las alcantarillas, donde se revela un gran laboratorio subterráneo.

Tras ser vencido, Krizalid insiste en activar a los clones pese a no poder acumular todo el poder del Equipo Hero, sin embargo, sus superiores lo deniegan, afirmando que los clones han sido reducidos por Heidern y sus hombres.

Tras salvar a sus antiguos camaradas, Kyo se marcha sin mediar palabra tras detectar el poder de su viejo rival, Iori Yagami.

En el juego del King of Fighters 99 existen tres finales secretos: