西洋妖怪の気配を感じて咲く髑髏彼岸の花が咲いた。日本の南端にある鬼界ヶ島に西洋妖怪が攻め込んできたのだ。妖怪横丁の妖怪たちに緊張が走る。鬼界ヶ島は西洋妖怪に占領され、島民たちはみな捕まっていた。人間に近い妖怪アマミ一族のミウは、弟のカイを逃がし、鬼太郎たちに助けを求めに行かせた。河原で釣りをしていたねずみ男は、力尽きたカイを偶然に救うが、カイを追って来た魔女に襲われる。そこに鬼太郎と一反もめんが助けにあらわれた。しかし魔女を捕まえるも、魔女見習いの孫娘ザンビアに隙をつかれ、取り返されてしまう。

カイから話を聞き、西洋妖怪との決戦を決意する鬼太郎たち。十二年前にも西洋妖怪は鬼界ヶ島を狙って猛攻撃をかけてきていたのだった。その時の戦いは熾烈を極め、西洋妖怪を退けたものの、ミウとカイの母親が犠牲となってしまった。そのことを鬼太郎は今でも激しく後悔していた。前回と同じく、子泣きじじい、砂かけばばあ、一反もめん、ぬりかべで決戦に赴くと言う鬼太郎。特訓しているみんなを見ながら、連れて行ってもらえないことをさびしく思うネコ娘に、子泣きじじいは前回の戦いの様子と鬼太郎の覚悟を伝え、諭すのだった。

地獄から閻魔大王の命によって、五官王が助っ人にあらわれた。目玉おやじは蒼坊主にも決戦に加わるように手紙を出したが、あいかわらず道に迷って合流できそうになかった。鬼界ヶ島へ旅立つ一行に、ネコ娘は霊界符を餞別に渡す。そしてねずみ男はこっそりついてきていた。鬼界ヶ島では、西洋妖怪が待ち受けていた。吸血鬼ドラキュラ三世、魔女ザンビア、狼男ワイルド、フランケン、そしてエジプトから来た妖怪王家の末裔、ミイラ男バルモンド。更にその手下のコウモリやオオカミ、ミイラ軍団など数千匹。ついに決戦が始まった！

雑魚を蹴散らし、フランケンと力勝負をする子泣きじじい、ザンビアと空中戦を戦う一反もめんと砂かけばばあ、コウモリ軍団に襲われるぬりかべ、ワイルドと剣を交わす五官王。そしてミウを助けに走る鬼太郎の前にバルモンドが立ちはだかった。髪の毛槍を突き刺し、体内電気を放つ鬼太郎、だがバルモンドは不死身だった。反撃され倒れ伏す鬼太郎に、バルモンドは島の秘宝、地獄の鍵は自分たちのものだと言い放つ。西洋妖怪が鬼界ヶ島を執拗に狙う理由はそれだったのだ。苦戦する日本妖怪たちは、はたして鬼界ヶ島を守れるのだろうか？！