謎の秘密結社『ネスツ』の存在が明るみに出てからしばらくの時が過ぎた。だが、それ以来ネスツはこれといった活動を起こすことなく影を潜めてしまう。

その一方、ネスツの動きとは対照的に、世界各地ではテロ活動が頻発する事態が発生。
ハイデルンたち傭兵部隊は、その活動がＫ´、マキシマの二人によるものであるということを掴む。

早速二人の追跡を開始しようとしたハイデルンだったが、
ちょうどその時『ＫＯＦ開催』の知らせが…！

世界各地でトーナメントを開始する格闘家たち。
驚くべきは招待チームの中にＫ´、マキシマたちのいるチームも存在したことだった！
さらに二人に引き寄せられるようにネスツも計画の第二段階を発動させる！！

ネスツの活動開始は単なる偶然か？それとも…！？

再び波乱の予感を漂わせ、ザ・キング・オブ・ファイターズいよいよ開幕……！！