《拳皇13》的故事主要圍繞著八神庵和草薙京的恩怨展開，同時也穿插了其他角色的故事，如盧卡爾、伊格尼斯等。遊戲中各個角色之間的關係錯綜複雜，不同的選擇和決定會觸發不同的劇情分支。
在故事中，玩家扮演的是草薙京，在和邪惡組織KOF對抗的過程中，結識了八神庵等一眾夥伴。但隨著故事的深入，盧卡爾組織也揭開了自己的面紗，對草薙京和八神庵等人的內心世界和記憶進行了調查，從而揭示了八神庵和草薙京之間的宿怨。在最後的決戰中，玩家需要決定是否和八神庵聯手對抗盧卡爾，或是選擇草薙一方。不同的選擇會帶來不同的結局。
此外，故事中還新增了合體技能系統，可以由草薙京和草薙柴舟組合出全新的技能，同時系統也新增了3D化的語音系統，可以更加真實地表現角色的情感。同時遊戲對原有系統進行大幅調整和簡化的必殺技系統，通過簡化釋放條件使出以往只存在於傳說中的招式。同時還可以體驗由各自對戰影響的故事模式。
總體來說，《拳皇13》通過豐富的角色、緊湊的劇情、新穎的系統和出色的視覺效果，為玩家帶來了一個充滿懸念、熱血與驚喜的故事。