西暦１６０５年。関ヶ原の合戦で、石田三成率いる西軍が勝利し、大坂に豊臣幕府が開かれて数年の時が流れていた。平和な京の都の一乗寺下り松では、総勢５０名を超える吉岡一門がムサシ（宮本武蔵）との決闘に臨んでいた。遅れて現れたムサシは、二刀流ならぬ二丁拳銃で、襲いかかる吉岡一門を撃破する。一方、幕府の本拠地・大坂城では、亡き秀吉の養女・カグヤ姫を狙って、空から怪しげな魔物が襲来してくる。奴らは――アヤカシ。その首領・ヤシャは、怪しげな妖術を使ってカグヤ姫を拉致していく。だがその行く手を遮ったのはムサシだった。ムサシは仲間である剣術の達人・ロウニンと共にヤシャからカグヤ姫を取り戻すことに成功するのだった。

ヤシャとの戦いの中で、銃を使った武道――ガン道の鍛錬が足りないことを悟ったムサシは、ガン道修業で有名な京都の大徳寺を訪れる。大徳寺のタクワン和尚といえば、ガン道を国中に広めた第一人者だった。一方、江戸では、江戸城主のリョウゲンの前にヤシャが現れていた。リョウゲンはカグヤ姫を嫁にめとって、天下統一を企んでいた。突然大徳寺を訪れたムサシに対し、寺の師範は、タクワン和尚は留守であると追い返そうとする。そこでムサシは師範とガン道勝負をして勝てばタクワン和尚に会わせろと決闘を申し込む。師範との決闘中、突如、アヤカシモンスター・ジジョウダが寺を襲撃する。ジジョウダの狙いはムサシ。ムサシはガン道で必死に戦うが、絶体絶命の危機に陥る。そんなムサシを、見事なガン道捌きで救ったのは、よぼよぼの寺男のじいさんだった。

寺男のじいさんの正体、それはタクワン和尚だった。だがタクワン和尚は、ムサシにガン道を教えようとはしなかった。そんな中、ムサシの命を狙う異国の美女・デスペラードがヤシャに拉致されてしまう。タクワン和尚から、ガン道の歴史、そしてにっくきライバル・佐々木小次郎について、数々の事実を聞かされるムサシ。そんな中、デスペラードが大徳寺に現れる。デスペラードは、アヤカシ女王蜘蛛モンスター・ガンダダーンの魔糸に操られていた。

アヤカシ女王蜘蛛に操られているデスペラードを助け出すことは不可能だった。そこへ現れたカラクリ屋の親父・荼毘の字が、ムサシに一発の銃弾を売りつける。その弾は火炎放射のごとく火を放ち、アヤカシ女王蜘蛛の魔糸を解かすことに成功し、ムサシはなんとかデスペラードを救うことができた。しかしその代償も大きかった。ムサシは二丁拳銃のうちの一丁を失ってしまう。そんな失意のムサシに、タクワン和尚は、自らの義手に隠した一丁の拳銃を授ける。それは『ガン鬼の銃』と呼ばれる伝説の銃だった。

アヤカシ女王蜘蛛は、総勢五十名を超える大徳寺の修行僧たちを魔糸で操り、ムサシを襲わせる。ムサシはガン鬼の銃を手に、銃の中に宿る鬼の夢幻世界を彷徨っていた。ガン鬼の銃は、手にした武士たちを鬼へと変える禁断の銃だった。鬼の呪縛から逃れるためには、強い精神力が必要。夢幻世界でムサシは、壊れかけそうな自らの精神をなんとか保って、現実世界へと舞い戻った。復活したムサシのガン道の腕は格段に上達していた。そしてガン鬼の銃を駆使して、ムサシはついにアヤカシ女王蜘蛛を撃破するのだった。勝利に酔いしれるムサシに、タクワン和尚は冷たく、お前もいつか鬼になると言い放つのだった。

ムサシが手にしているガン鬼の銃はガン鬼の天と呼ばれる銃であり、ガン鬼の銃にはもう一丁、ガン鬼の地と呼ばれる銃があるという。そのガン鬼の地を手に入れない限りは、ムサシもいずれ心を鬼に食い尽くされ、発狂して果てるとタクワン和尚は脅す。ではガン鬼の地はどこにあるのか？そのヒントは、かつてムサシが持つガン鬼の天を手にしてしまったがために、発狂してしまった男の言葉に隠されているという。その男の名は明智光秀。本能寺の変で明智光秀が織田信長を殺したのは、ガン鬼の天を持ったことで心を鬼に支配されてしまったのが原因だった。信長の首を取った明智光秀は、駆けつけた荼毘の字に意味深な言葉を呟いた。ガン鬼の地は月にあると。ガン鬼の地を探して旅に出ることを決意するムサシ。一方、大坂城では、カグヤ姫が馬を駆って城を脱走していた。

大坂城を出たカグヤ姫を、ヤシャが再び拉致しようとアヤカシカラスを出動させる。一方、旅に出たムサシとロウニンの目の前に、一人の青年武士が現れる。青年武士の名は、徳川秀忠。徳川家康の息子である。徳川秀忠は、初対面のムサシに対し、父親である家康暗殺を依頼するのだった。徳川秀忠によって明らかにされる家康とアヤカシとの関係。なんとリョウゲンは家康がアヤカシに魂を売り渡したなれの果てだった。そんなムサシたちの前に、アヤカシカラスに拉致されたカグヤ姫が通りかかる。ムサシはガン鬼の銃を使って、アヤカシカラスを退治する。意識を取り戻したカグヤ姫に、今度は徳川秀忠が刀を抜いた。徳川秀忠はカグヤ姫を殺そうとしていた。

何故に徳川秀忠がカグヤ姫の命を狙っているのか？その答えは、徳川家康がアヤカシに魂を売り渡した過去にあった。関ヶ原の合戦で、東軍が敗北して間もない頃、失意の中の徳川家康の元にヤシャが姿を現す。ヤシャは、この歴史は間違った歴史であり、本当の歴史では、徳川が日本を支配しているのだと告げる。どうすれば本当の歴史に戻るのかと問う徳川家康に対し、ヤシャは、アヤカシになり、カグヤ姫を嫁にめとることこそがその近道であると告げるのであった。それら事実を知るムサシとロウニン。そんな二人の前に、突如、幼い美少女が助けを求めて山の斜面を転げ落ちてくる。ユメ姫だった。ユメ姫は、真田幸村の一行から命からがら逃げてきたのだった。気絶したユメ姫をめぐり、真田幸村とムサシが今、対峙する。

ユメ姫を奪還しようとする真田幸村は、部下の真田十勇士を使い、ムサシとロウニンに戦いを挑んでいく。十勇士の中でも、霧隠才蔵、三好清海入道、根津甚八の三人の強さはすさまじく、さしものムサシとロウニンも苦戦する。そんな中、カグヤ姫とユメ姫の前に、小早川秀秋が現れた。小早川秀秋は、カグヤ様とユメ姫を拉致し、そしてムサシと真田幸村に対し、二人の姫を返してほしければ、城盗り勝負をしろと言い残し、去っていくのだった。

石田三成の古城にて城盗り勝負が開始される。お宝は、天守閣に拉致されているカグヤ姫とユメ姫。ムサシと真田幸村は、仕掛けられた数々のトラップに苦戦しながらも、互いに一歩もひかず、天守閣へと攻めていく。そこにこの城盗り勝負を仕掛けた小早川秀秋が参戦してくる。小早川秀秋の真の狙い、それは、二人の姫ではなく、ムサシの持つガン鬼の銃を奪うことだった。小早川秀秋は伝説の銃を手に、関ヶ原の功労者である自分を座敷牢へと閉じこめた石田三成や幕府首脳への復讐を企んでいたのだった。ムサシは一瞬の隙をつかれ、ガン鬼の銃を小早川秀秋に奪われてしまう。計画通り、ガン鬼の銃を手にした小早川秀秋だったが、ガン鬼の銃の中に宿る『鬼』に精神を破壊され、完全に錯乱状態となってしまう。錯乱した小早川秀秋がムサシを襲う。絶体絶命のムサシを救ったのはユメ姫だった。ユメ姫は、咄嗟に不思議な超能力でムサシのピンチを救った。その様子をヤシャが不吉なまなざしで眺めていた。

ガン鬼の銃をムサシから騙し取った小早川秀秋は心を鬼に支配され、次第に正気を失っていく。ムサシ、ユメ、真田幸村たちが、小早川秀秋の錯乱に戸惑う中、カラクリ馬車に乗った荼毘の字が古城に駆けつける。古城の至る所でムサシたちを苦しめたカラクリ武者人形はやはり荼毘の字の発明品だった。カラクリ武者人形の修理をはじめる荼毘の字の前に突如、ヤシャが姿を見せる。意外にも、ヤシャと荼毘の字は顔見知りであり、更に驚くことに、荼毘の字はヤシャに協力を申し出るのだった。実は荼毘の字の正体は、伊太利亜の天才芸術家にして天才科学者、レオナルドダビンチだった。百年前死んだはずのダビンチを生き返らせ、日本に復活させたのも全てヤシャの仕業だった。そんな中、荼毘の字のペットモンキー・猿飛佐助が人間の姿に変化する。実は、猿の猿飛佐助は本当は人間だった。それも真田十勇士の一人、天才忍者の猿飛佐助だったのだ。人間の姿に戻った猿飛佐助は、ムサシのへっぽこ子分・ニンジャ太郎と瓜二つだった。ヤシャは、荼毘の字、そして意識を失った小早川秀秋と共にテレポーテーションして消え去っていくのであった。

どうして人間の猿飛佐助が猿になっていたのか？その答えにもまたヤシャと荼毘の字が深く関与していた。今から一年ほど前、猿飛佐助は、真田幸村の命令で、荼毘の字のカラクリ屋に忍び込んでいた。その時、カラクリ屋にヤシャが現れ、猿飛佐助は危うく殺されかけるが、荼毘の字に救われ、猿の姿に変えられた。ヤシャは、七つ揃うとアヤカシを封じ込めることが出来るという伝説の封印魂を探索するレーダーの発明を荼毘の字に依頼していた。そして一年後、人間の姿に戻った猿飛佐助は、ムサシに一発の銃弾を手渡す。銃弾の中には、荼毘の字から託された封印魂の在処が記された秘密の地図が隠されていた。ムサシは、ロウニン、ユメ、ニンジャ太郎と、そしてカグヤはダンジョウ、猿飛佐助と共に、それぞれ別行動で封印魂を探す旅に出る決意をする。そんなムサシの前に、突如、強大なアヤカシが出現する。虎と人間のキメラ――風林火山の軍旗に、勇ましい鎧甲……彼こそは、ヤシャと荼毘の字がタッグを組んで作り出した戦国武将の魂を持つキメラアヤカシだった。そう、その戦国武将とは武田信玄！ムサシの全く新しい戦いの火ぶたが、今、始まろうとしている！

キメラアヤカシ武田信玄の強さは尋常ではなかった。ムサシは、アヤカシ信玄の作り出した戦国バトル亜空間へと引きずり込まれる。ガン鬼の銃を駆使して、アヤカシ信玄と懸命に戦うムサシ。しかしアヤカシ信玄の強さは圧倒的だった。絶体絶命の危機に陥るムサシ。だがアヤカシ信玄はとどめを刺すことを止め、姿を消すのだった。気を取り直して封印魂の一つ目の城を目指すムサシたち。一方、ヤシャは、荼毘の字がムサシに封印魂の地図を渡したことを知り、容易に封印魂をゲットできないよう、七つの城に強力な妖術をかけるのだった。ついに第一の封印魂が隠された城へと辿り着くムサシたち。だがそこは深い湖に水没してしまった城だった。その上、湖と城全体にはヤシャの妖術による数々のトラップが仕掛けられていた。苦戦するムサシたちだったが、ユメとロウニン、そしてデスペラードの協力で、なんとか一つ目の封印魂を手にすることに成功するのだった。しかし、そんなムサシの前に、突如、最強のカラクリ魔神が現れる。

ムサシが手に入れた封印魂は、ラセツのよって奪われてしまった。失意に沈むロウニンたち。一方、ムサシは奪われたら奪い返すまでと闘志を燃やし、第二の封印魂を目指す旅を急ぐ。そんなムサシたち一行に合流する女が現れる。デスペラードだ。デスペラードは、タクアン和尚からムサシに、ガン鬼の銃の新しい銃弾を渡すよう、託されたのだった。デスペラードを仲間に加え、旅を続けるムサシたちはついに第二の封印魂が眠る城へと到着する。だがそこには陰陽師の新たなトラップが仕掛けられていた。

第二の城のトラップ――それは、過去の自分との壮絶なる殺し合いだった。ムサシたちはそれぞれ、小部屋に閉じこめられる。小部屋では、陰陽道によって召還された過去の自分が姿を現す。そしてお互い、命果てるまで殺し合うのだという。部屋から脱出するためには、過去の自分を殺せばいい。だが過去の自分を殺せば、現在の自分もまた消滅してしまう。このタイムパラドックスに、ムサシたちは手も足も出ない状態で苦しみ抜くのだった。

ムサシたちが過去の自分との壮絶なる殺し合いに苦しんでいる頃、ヤシャの庇護を受けるレオナルドダビンチこと荼毘の字は、ラセツが持ち帰った封印魂の分析をはじめる。すると封印魂から光が放射され、一人の陰陽師がホログラム映像として出現する。その名はウラシマ。封印魂を七つの城に隠し、様々なトラップを仕掛けた張本人である。ウラシマは、一つ目の封印魂がアヤカシの手に落ちていることを知るや、ムサシたちに加勢するべく第二の城へとテレポーテーションする。そして、ムサシたちにテレパシーでアドバイスを送り、タイムパラドックスを回避させることに成功するのだった。

ムサシたちとは別行動で封印魂を探し求める旅を続けていたカグヤ、ダンジョウ、猿飛佐助は、西国の鍾乳洞内部で、謎のアヤカシと遭遇する。そのアヤカシこそは、ヤシャによって滅ぼされた元祖アヤカシの気の塊であった。そんな中、カグヤたちの前に、ヤシャと陰陽師ウラシマが同時に姿を現し、そしてヤシャとウラシマは対峙し合うのであった。一方、ムサシは、不注意から誤って池の中に、せっかく手に入れたばかりの封印魂を落としてしまう。池の底から、封印魂を探し出してきたのは、あのカラクリ巨人・ラセツだった。今、ラセツ対ムサシの壮絶なるバトルが再び開始される。

鍾乳洞では、ヤシャとウラシマ、互いの存在を賭けた決死の戦いが繰り広げられていく。一方、ムサシとラセツも、亜空間でのバトルを開始する。その頃、江戸では、荼毘の字とリョウゲンが、ヤシャのテレポーテーションシステムを応用したカラクリマシンの試運転を開始していた。だがリョウゲンのミスにより、マシンは爆発、それによって時空に歪みが生じ、猿飛佐助とニンジャ太郎の体が強制的に融合させられる。２人は元々同一人物だった。この機を逃さず、ウラシマがヤシャを自分の体の中へと封じ込めることに成功する。ヤシャとウラシマもまたかつては同一人物だったのだ。

ヤシャを体内に封印し、肉体と意志を取り戻したウラシマは、リョウゲンとアヤカシ武田信玄の抹殺を計画する。まずはアヤカシ武田信玄を抹殺、続いてリョウゲンを狙うが、ウラシマ本人は直接リョウゲンに手を下すことはしないという。そしてウラシマは言う。リョウゲンを抹殺するのは宮本武蔵であると。その言葉通り、ウラシマは、リョウゲンとムサシを亜空間へと導き、それで互いの命を賭けた戦いを命じるのだった。

陰陽師ウラシマの策謀により、リョウゲンと戦うことになったムサシ。だがムサシもリョウゲンも、お互いが敵同士でありながら、同じ目的に向かって戦っていることの虚しさに気づいていく。一方、４つ目の封印魂を求めて、カグヤ・ダンジョウ・猿飛佐助たちグループと、ロウニン・デスペラード・ユメたちグループは、それぞれ別々の城へと辿り着いたはずだった。それぞれのグループに謎のアヤカシ集団が突如襲いかかる。だが、そのアヤカシ集団は、姿こそアヤカシだが、実は、それぞれカグヤたち、ロウニンたちだった。カグヤたちには、ロウニンたちがアヤカシの姿に見えて、反対にロウニンたちには、カグヤたちがアヤカシに見えるのであった。壮絶なる相討ち合戦を続けるカグヤたち、そしてロウニンたち。だが戦いの中で、お互いが味方であることが分かり、刀を収める。そして戦うことの虚しさを知るのであった。

戦うことの虚しさ、無意味さを知り、戦意喪失してしまうムサシたち。そんな中、それまで過去の記憶を失っていたユメが、その記憶を開封させ、懐かしい歌を口ずさむ。その歌こそは、カグヤとユメの出生の秘密を紐解く歌だった。ユメとカグヤが懐かしそうに口ずさむ歌を、ウラシマが耳にした途端、ウラシマが苦しみ、激昂していく。一方、ムサシとのバトルの中で、アヤカシに魂を売り渡してまでも求めていた天下取りに、疑問を抱き始めたリョウゲンは、荼毘の字と共にヤケ酒を飲み暴れるのであった。

酒に酔った荼毘の字とリョウゲンは、ヤシャがいなくなり、いまや誰も命令する者がいなくなったラセツを改造して、ある命令を下すのであった。５つ目の封印魂を求め、旅を続けるムサシたちの前に、突如、ラセツが現れる。ラセツの手には、先回りして手に入れた５つ目の封印魂が。ラセツが、ダンジョウ、デスペラード、猿飛佐助を襲う！だがラセツの目的は、ムサシの持つ４個の封印魂でもなければ、ムサシたちの命でもなかった。ラセツは手にした大きな筆で、ムサシたちの顔や胸や背中に落書きをして回る。それこそが、リョウゲンと荼毘の字の下した命令だった。苦戦しつつも、ムサシたちは、一同の力を結集させて、ついにラセツを破壊するのだった。

６つ目の封印魂の在処は、日本海に浮かぶ佐渡島。そこに、全て金で出来たお城があるという。ムサシ、ロウニン、ダンジョウ、猿飛佐助たち男性陣と、カグヤ、ユメ、デスペラードの女性陣は、男と女に別れて、金の城へと潜入、壮絶なるバトルの末、ついに６つ目の封印魂をゲットするのだった。

最後の封印魂は、九州阿蘇の溶岩城の中に隠されていた。ムサシは、ロウニンたちの助けを借りて、一人、ドロドロの溶岩で囲まれた灼熱の城の中へと潜入する。だがそこにあるはずの７つ目の封印魂は既に何者かによって奪われた後だった。ムサシより先に７つ目の封印魂を奪った人間――それは、ムサシの永遠のライバルであり、ムサシがこの世で一番避けている人物――佐々木小次郎その人だった。だが佐々木小次郎の姿を見て、ムサシとロウニン以外の仲間たちは唖然とする。なぜならば、佐々木小次郎が絶世の美女だったからだ。

ムサシがなぜに佐々木小次郎を嫌っていたのか？その理由がついに明らかにされる。佐々木小次郎はずっと前からムサシに恋をしていた。そして自分との戦いに勝てば、結婚してくれと申し込んでいたのだった。ムサシは、その申し出そのものを拒絶する。そんな中、７つ全ての封印魂が揃ったのを待ちかねたように、ウラシマが現れ、ムサシたちを大坂城へとテレポーテーションさせる。大坂城では、ムサシたちに対抗するべく、石田三成と真田幸村たちが厳重なる警護を固めていた。そのど真ん中に、現れたムサシたちは、壮絶なる戦いを繰り広げながら、城の奥へと突き進む。そして、ついに封印魂の儀式が始まるのだった。ウラシマが、なぜ故に、ヤシャを倒し、ムサシたちを使って、封印魂を集めたのか？その理由は一つ。太閤、豊臣秀吉を蘇らせるためだった。棺の中に眠る秀吉のミイラ。その手には、なんと、ムサシが求め続けたもう一丁のガン鬼の銃が握りしめられていた。ウラシマの正体が明らかにされるとき、蘇った豊臣秀吉がムサシに迫る！