明治十六年。剣心が不殺を誓った流浪人として東京に流れ着いて５年。神谷道場に、剣心の宿敵・志々雄の遺刀「無限刃」を継ぐ青年・明日郎と、白人との混血児・阿爛、更に謎の女・旭を道場に迎え、かくも平穏な日々を過ごしていた。
そんな中、西南戦争で死んだはずの薫の父・越路郎が北海道・函館で生きていることが判明。剣心と薫は越路郎を迎えに函館に行く事を決める。
捕らわれの劍客兵器・凍座から情報を引き出すため五稜郭へやって来た剣心。ずっと口を閉ざしていたという凍座は剣心を見るなり固い握手を交わし、待ちわびた猛者との邂逅を喜び、剣心の問い「劍客兵器とは何か、その目的は何か」に答え始めた――。
劍客兵器…それは鎌倉時代、モンゴルからの日本侵攻を二度にわたり阻止した武士たちの末裔であり、次なる外海からの侵略に備えるべく志を持ち集まった者たち…つまり自分たちこそ護国の切り札だという。
さらに、歴史の闇で鍛え続けた彼らが何故今姿を現したのか、それは開国し明治を迎えた日本に待っているのは外国との戦争であり、その戦で勝つためには実戦の“場数”を踏む必要があると言う…つまり争いを故意に起こし、強制的に実戦経験を積ませるためだった。
劍客兵器の恐るべき全貌が明らかになったその時、札幌の刑務所・樺戸集治監が襲撃されたとの知らせが舞い込む。劍客兵器の目的は、諸外国との戦争に勝利するという希望のため、函館だけでなく北海道全域を戦場という絶望に落とし、彼我問わず、猛き戦闘者を育成すべく“実検戦闘”をしようというものだった…!!
そして、凍座は改めて剣心に告げる――「絶望と希望の大地へようこそ！」と…。