Os quatro primeiros jogos da série giram em torno dessas lutas, enquanto The King of Fighters '99 introduz um novo arco de história, girando em volta de K', um jovem que busca destruir a misteriosa organização NESTS porque eles o sequestraram quando era jovem e o despojaram de suas memórias passadas, para que pudessem forçá-lo a ser um lutador sob seu controle.