明治十六年。剣心が不殺を誓った流浪人として東京に流れ着いて５年。神谷道場に、剣心の宿敵・志々雄の遺刀「無限刃」を継ぐ青年・明日郎と、白人との混血児・阿爛、更に謎の女・旭を道場に迎え、かくも平穏な日々を過ごしていた。 そんな中、西南戦争で死んだはずの薫の父・越路郎が北海道・函館で生きていることが判明。剣心と薫は越路郎を迎えに函館に行く事を決める。
凍座が仲間から実検戦闘再開の報を受け、斎藤を通し剣心たちは五稜郭近郊の兵舎に呼び出された。そこで斎藤が、三島を対劍客兵器の隊に入れることを宣言。しかし、三島にとって故郷の仇である志々雄一派・十本刀が仲間に加わっていることを知る剣心は猛反対する。
そんな最中、十本刀の面々が合流し、三島は怒りに任せ宗次郎に銃を向ける。しかし、安慈和尚の“礼”を尽くした行動と、永倉の説得でその場での復讐は回避された。斎藤は、仇と共に劍客兵器と戦うか否かを三島本人に委ね、彼一人を残し皆で五稜郭へと向かうのだった。
そうして訪れた五稜郭、剣心と斎藤は次なる実検戦闘の場所を聞き出すため、凍座の房へ足を踏み入れる――!!