在KOF97结束后，KOF98开始了，这次KOF大赛算是让新人们松了口气，因为参加大赛的拳皇角色少了很多，这次任务算是简单的度过了。98年平静的过去了，99年到了。
“召开KOF”——世界各地的格斗家们又收到了邀请函。格斗之王大会将再一次召开！但是这次的气氛似乎有些不同。在招待者的背后，似乎完全没有那种世界大会般规模的支持者。在格斗家们觉得不可思议的时候，对战形式又出现了新规定。
“对战形式仍为3对3，但大会采用援护战斗的形式。”
“援护战斗!”，听到这个陌生名词的格斗家们掩饰不住脸上的困惑。感觉到有些火药味的哈迪伦示意拉尔夫等人参加战斗，查明大会开展的真相。
其中，二阶堂红丸也作为特别队的一员收到了邀请，预备出席KOF。队友的名字是K‘以及麦克西姆（Mjximj）。但是在以前的格斗界中，红丸对这两个名字闻所未闻……满怀心事的红丸以及格斗家们分别动身前往指定地点，他们心中充满疑惑——援护模式是什么？这次举办的大会又有什么内幕？满是谜团的KOF即将再掀风雨！
在KOF99大会开始不久，世界各地出现大批克隆人战士和改造人战士出现，它们的背后，是阴森庞大的神秘组织——NESTS。而克隆人的相貌，赫然竟是世人心目中的英雄——京。
原来，NEST·S表面上是一个知名的国际企业，实际上却是一个企图征服世界的庞大组织。趁着上次拳皇大会草薙京和大蛇战斗后身体极度虚弱的时机，将其捕获，并利用京的身体进行了一个名为“ProjectK”的计划，计划内容包括京的克隆、京的战斗数据分析和把”最终决战奥义·无式”分析并将其数据化，还有京的基因移植等。K‘和Krizalid就是这计划下的产物。后来，八神庵闯入京身处的研究所大肆破坏，谁知破坏所产生的震动却意外令京苏醒，京也因此而逃离了NEST·S，并行踪不明。
K’他们胜出了大会，并且和NEST·S的干部Krizalid会面。从Krizalid的口中得知，一切都只是为了替复制草薙京军团收集「引子数据」：由于京一生中从没杀过一个人，造成了京的复制人有”无法杀人”的缺陷，因此要收集一些杀人的数据然后将之输入复制人的脑内来填补他们的缺陷。至于收集引子数据的方法，就是和Krizalid战斗后再透过Krizalid的特制衣服传送给布置于世界各地的复制京。在此之后，复制京们便会向各国首都发动袭击，藉此令各国元首投降，轻易征服全世界。可是，本是完美的计划却因为Krizalid的战败而宣告破产，Krizalid更因此而被NEST·S的高层废弃;在临死前更从自己认为是“姊姊”的Whip口中得知自己是K’的复制人，令一直以为K’是自己的复制品的Krizalid大受打击，含恨而终。因为这一次的失败，令NEST·S这个组织的存在曝光。，开始受到军方的关注。
在KOF99结束后谢道带着妹子们很是开心的到处摧毁NEST·S的基地，不得不说谢道总算是记起自己拯救世界的口号了。这回谢道是彻底与NEST·S干上了，嗯，话说NEST·S的科技还是很不错的，谢道也是窝在家里爆完科技才敢出来与NEST·S硬抗。