アメリカ独立戦争で戦っていたイカボッド・クレーンは21世紀のスリーピー・ホロウで目を覚ます。町ではコービン保安官が、同じく目を覚ました首なし騎士に首を切られて殺されてしまう。相棒のアビー・ミルズ警部補は、最初クレーンの話を信じなかったが、自身の子供時代の奇妙な体験を思い出し、共に事件の謎を追うことに。だがアビーの上司、アーヴィング警部はクレーンの突拍子もない話や超常現象に懐疑的な態度を示す。

妻のカトリーナから悪魔の手下が現れると夢で警告を受けるイカボッド。イカボッドとアビーはコービン保安官が残した資料から、その手下が満月(ブラッド・ムーン)の夜に復活する魔女であることを突き止め、何とか魔女の復活を防ごうとする。一方、首を折られ、死んだはずのブルックスは悪魔の使いとなり、魔女の手伝いをしていた。魔女は自分を処刑した判事の子孫の灰を集め、自身の骨を捜し出し、復活を図ろうとする…

サンドマン(眠りの精)の悪夢を見たアビー。直後、スリーピー・ホロウの医者と牧場主が謎の自殺を遂げる。彼らはアビーを含め、アビーの妹ジェニーと関係がある者だった。アビーはイカボッドの提案で、精神科病院にいるジェニーと面会しようとするが、拒絶される。アビーとイカボッドは、サンドマンは悪魔の手下であり、次の狙いがアビーだと知ると、先住民の子孫に助けを求める。アビーは夢でサンドマンと戦うことになるが…

アビーとイカボッドは病院を脱走したジェニーを捜し、コービン保安官の小屋で見つける。ジェニーは保安官に頼まれ神秘的な物を集めてたが、その1つ、六分儀が謎の集団に奪われてしまう。六分儀は第7の地獄への戸口を開く「ソロモンの小さな鍵」の本の隠し場所が分かる道具であった。六分儀を手にしたのは、悪魔の手先であり、首なし騎士と同じ雇い兵の集団。彼らは本を使い、閉じ込められた悪霊たちをこの世に放とうとしていた。

謎の病気で倒れた身元不明の少年が森の近くで発見される。スリーピー・ホロウでは少年と同じ病気に感染した者が続出。アビーとイカボッドは手がかりを求めて少年が見つかった森へ向かう。そこで2人は16世紀に突然姿を消した町、ロアノークを発見する。集落の人々も少年と同じ病気を患っていた。アビーとイカボッドは少年や感染者を救うため、治療法があるとされる集落へ少年を戻そうとするが、イカボッドも感染してしまう。

イカボッドが何者かに拉致され、アビーの前にカトリーナが姿を見せる。彼女は首なし騎士がその晩復活すると予言。カトリーナの言葉の下、アビーはイカボッドと首なし騎士の混ざりあった血を取り去るため、"シン・イーター"と呼ばれる悪霊を体内に取り込み退治する人物を捜すことになる。一方で、連れ去られたイカボッドは首なし騎士との戦いを模索するある人物と対面。カトリーナとの最初の出会いについて思い返していく。

フリーメイソンのメンバーが首なし騎士に殺され、首なし騎士が首を取り戻そうとしていると気づくイカボッド。アビーとイカボッドは首なし騎士の頭蓋骨を破壊しようとするが、何をしても壊れない。アビーのもとには死んだはずのアンディが現れ、騎士は殺すことはできないが捕まえることはできると伝える。さらにアビーたちは首なし騎士に関する秘密文書が存在することを知り、その文書をもとに首なし騎士を捕らえる作戦を決行する。

イカボッドは死人のブルックスを介し、捕まえた首なし騎士を尋問する。騎士がカトリーナのネックレスを持っていることに気づくイカボッド。そしてついに騎士の正体が明らかになる。首なし騎士はイカボッドの元親友であり、カトリーナの元婚約者のエイブラハムだった。停電により力を回復していく騎士。ブルックスが手にした聖杯で牢屋の魔法は解かれ、解放された騎士はイカボッドを殺そうとするが、モロクの手下たちが現れ…

イカボッドとアビーは失踪した"建国の父"の子孫リナの捜索に当たる。リナは先祖の屋敷を訪れた後、姿を消したが、その屋敷はかつてイカボッドが妻のカトリーナと訪れた場所であった。所有者であるリナの先祖は、屋敷を元奴隷や悪魔から逃れる人々の避難所として提供していたのだ。屋敷で悪霊に囚われていたリナを救い出すイカボッドとアビー。そこでアビーは家政婦の長の霊に導かれ、カトリーナが男の子を出産するのを目撃する…

イカボッドは息子のことを調べるため、罪食い人のパリッシュを介し、煉獄にいるカトリーナと接触を試みる。煉獄から戻ったイカボッドはアビーらと共に息子のジェレミーの消息を追う。だが同時にジェレミーが自分を守るために作った怪物"ゴーレム"が煉獄から現れ、母親を奪った仲間の魔女団のメンバーたちに復讐を始める。つらい人生を送り、命を絶たれた息子を思いつつ、イカボッドはゴーレムを何とかなだめようとするが…

モロクの手下であり、人間に憑依する悪魔 アンシーティフが、アーヴィング警部の前に現れ、イカボッドが持つワシントンの聖書を差し出さなければ、娘を奪うと脅しをかける。悪魔払いの方法を調べるイカボッドとアビー。だがその途中、過去にジェニーがアンシーティフに憑依されていたことを知る。アビーたちは悪魔払いができる古代のランタンを探し出し、何とか手に入れようとするが、アンシーティフが警部の娘に取りついてしまい…

イカボッドとアビーはワシントンの聖書に煉獄へ導く地図の在りかが隠されていると知る。罪食い人のパリッシュの力を借り、地図を探す2人。イカボッドは地図が手に入ればカトリーナを救い、モロクに勝てると考えるが、アビーは煉獄にいるカトリーナを解放すれば、逆に終末が始まるのではと危惧する。アビーはさらに証人の1人が裏切るという預言が気になっていた。2人はワシントンの遺体と一緒に埋められた地図を手に入れるが…