世界格斗豪强再次收到“KOF”的邀请函。邀请者还是“R”，难道是前一年在航母上自爆的RUGAL？
《格斗之王95》与KOF94相比较，KOF95最大的改变既是取消了以国家作为单位，而改为以人物为单位的选取方式，并且追加了一种人物自由组合的设定。登场人物也有所改变，原KOF94的美国队三位角色不再登场，而新加入了几名角色。
背景设定
这一次出场的队伍中，来自“饿狼传说”系列的棍王比利和“龙虎之拳”系列的忍者如月影二，还有草薙京一生的宿敌，那就是八尺琼家的后人八神庵组成的“劲敌队” ，击败了在KOF94中表现不俗的美国运动队，获得比赛资格。
那么，比利会有什么阴谋？如月又有什么样的野心？还有，京的宿敌八神，又是怀着什么样的心态参战的呢？席卷着巨大阴谋的KOF大会再次展开……
大会到了最后，京击败了所有对手，却中了睡眠瓦斯而昏睡过去。当他醒来时，发现RUCAL竟然还活着，并且正是此次大会的主办者。此时京的父亲草薙柴舟再度出现，但是已经被卢卡尔洗脑，敌我不分地和京战斗起来。经过痛苦的战斗，京打败了父亲，并将之救回，然后和队友们一同杀向幕后黑手RUGAL。
拥有带着神秘而恐怖的力量的卢卡尔轻易打倒了所有对手，就连京也被逼得山穷水尽一筹莫展。正在所有人绝望之际，卢卡尔却因为体内的力量反噬而死。
从此以后，京和庵开始了恒久的对立，一正一邪。一个象征太阳，一个象征月亮。而两人的联手，必是天地风云变色之时。
出招表
主人公队
草薙京(KYO KUSANAGI)
摔）一刺背负投：→或←+C
外式·轰斧阳：→+D
八拾八式：↘+D
外式·奈落落：(空)↓+C
百八式·暗杀炎：↓↘→+A或C
百式·鬼烧：→↓↘+A或C
百壹式·胧车：←↓↙+B或D
贰百拾二式·琴月阳：→↘↓↙←+B或D
七十五式·改：↓↘→+B》B或D》D
*里百八式大蛇薙：↓↙←↙↓↘→+C
二阶堂红丸(BENEMARU NIKAIDO)
飞跃踹踢：(空)↓+D
背倒摔：→或←+C或D
急速膝摔：(空)↓+C或D
雷刃拳：→↓↘+A或C
居合踢：↓↘→+B或D
真空片手驹：→↘↓↙←+B或D
超级闪电踢：↓↑+B或D
反动三角蹴居合踢中：↓↑+B或D
*雷光拳：↓↘→↓↘+C
大门五郎(GORO DAIMON)
摔）扫脚摔：→或←+D
十字锁：→+C
横车：←+C
地雷震：→↓↘+A或C
超受身：↓↙←+B或D
天地摔：(近)→↘↓↙←→+C
超大外割：(近)→↙↓↘+D
抓云投：(近)←↙↓↘→+A
残株摔：(近)←↙↓↘→+C
*地狱极乐落：(近)→↘↓↙←×2+C
