鬼太郎と目玉おやじは、見覚えの無い場所に立ち尽くしていた。ねずみ男が持ってきた、 妖怪ポストに入っていた鵺（ぬえ）からの手紙を見て、京都の鵺寺を訪れたのだが、本堂からわきだした黒雲につつまれ、気が付いたらここに来ていたのだ。鵺とは、黒雲に覆われ、その正体を見たものが無く、おそろしい妖怪だと伝えられており、鵺寺に封印されたと言い伝えられていた。困惑した鬼太郎は、通りの方で数多くの付喪神（つくもがみ）が陰陽師たちの操る式神に追われているのを見る。式神に捕らえられた付喪神は石灯籠に変えられてしまうのだ。

必死に逃げる付喪神たちを鬼太郎は助け、都の出口である羅生門に向かう。しかし羅生門は現代には残っていないはず。鬼太郎と目玉おやじは、1200年前の京都、平安京にタイムトリップしてしまったことを知る。羅生門の上で付喪神や羅生門の鬼に話を聞くと、鵺が人間をおそうので陰陽師たちが妖怪狩りを行うようになったのだと言うが、その正体は誰も知らなかった。琵琶の付喪神に鵺が出ると言われる場所へ案内してもらう。途中、母子連れに出会うが、妖怪を恐れない様子に、鬼太郎はこの時代は妖怪と人間が共存していたことを知るのだった。

待ちかまえていた陰陽師たちに追い詰められる鬼太郎。鵺が凶悪な妖怪だという噂を流し、陰陽師たちを操ってけしかけていた者の正体は化け灯籠だった。雷を操るその力は強く、また人間を盾にしたので、鬼太郎は手が出せずに石灯籠にされてしまう。鵺も手出しができなかったので封印してやったと笑う化け灯籠。鵺は本当は人間に味方する良い妖怪だったのだ。目玉おやじの活躍で封印の札がはがされ、復活した鵺により、鬼太郎は元の姿に戻ることが出来た。雷によって平城京に起こった火事を、鵺は残り少ない妖力を使って消していくのだった。

鬼太郎は戦いの末、化け灯籠を倒した。石灯籠から元の姿に戻れた付喪神たちは、鬼太郎を讃えながら喜びの行進、百鬼夜行（ひゃっきやぎょう）を繰り広げた。鵺の功績をみんなに訴えようとする鬼太郎に、鵺は自分は醜く、声も恐ろしいので誰に知られずともよいと語り、最後の力を振り絞って鬼太郎を元の時代に戻す。現代に戻って、鵺寺でネコ娘とねずみ男に再会した鬼太郎は、鵺寺が鵺を讃えるために作られたことになっており、鵺が恐怖の対象ではなく崇拝されるようになっていることに気付く。鵺の行為は報われ、歴史が変わったのだった。