In 1799, New York City police constable Ichabod Crane (Johnny Depp) is facing imprisonment for going against traditional methods. Ichabod submits to deployment to the Westchester County hamlet of Sleepy Hollow, New York, which has been plagued by a series of brutal slayings in which the victims are found decapitated: Peter Van Garrett (Martin Landau), a wealthy farmer; his son Dirk; and the widow Emily Winship. Crane is informed that the killer is an undead headless Hessian mercenary from the American Revolutionary War who rides on a black steed in search of his missing head.
Crane begins his investigation, remaining skeptical about the supernatural elements until he actually encounters the Headless Horseman, who kills the town magistrate, Samuel Phillipse (Richard Griffiths). Boarding at the home of the town's richest family, the Van Tassels, Crane is taken with their daughter Katrina (Christina Ricci). Crane and Young Masbath, the son of one of the Horseman's victims, go to the cave dwelling of a reclusive sorceress. She reveals the location of the Tree of the Dead, which marks the Horseman's grave, as well as his portal into the natural world.
Crane discovers that the ground is freshly disturbed and the Horseman's skeleton has the skull missing. He realizes that whoever dug up and stole the skull is the person controlling the Horseman. The Killian family are taken by the Horseman and Katrina's suitor Brom van Brunt (Casper Van Dien) is killed trying to stop the Horseman.
Crane starts to believe that a conspiracy links all the deaths together, so he looks into Van Garrett's Last Will. Van Garrett had made a new will just before he died, leaving all his possessions to his new bride, Emily Winship. Crane deduces that all who knew about the new will were the victims of Horseman and that Katrina's father Baltus Van Tassel (Michael Gambon), who would have inherited the fortune, is the person holding the skull. Katrina, finding out that Crane suspects her father, burns the evidence that Crane has accumulated.
A council is held in the church. The Horseman seemingly kills Katrina's stepmother, Lady Van Tassel, and heads off to the church to get Baltus. Crane realizes the Horseman can't enter the church due to it being holy. A fight breaks out in the church and the chaos ends only when the Horseman harpoons Baltus through a window, dragging him out and acquiring his head. The next day, Crane believes Katrina to be the one who controls the Headless Horsemen.
Crane becomes suspicious when the corpse of Lady Van Tassel has a wound that seems to have been caused post-mortem. The real Lady Van Tassel (Miranda Richardson) then emerges, alive. Lady Van Tassel tells Katrina that her family was driven from their ancestral home by the Van Garretts, and that she became a witch and summoned the Horseman to kill them off and make herself sole heir to the family fortune. She then sends the killer after Katrina to solidify her hold on what she considers her rightful property.
Following a fight and a stagecoach chase, Crane eventually thwarts Lady Van Tassel by throwing the skull to the Horseman, which causes his head to become reattached to his body and the curse broken. The Horseman, no longer under Lady Van Tassel's control, simultaneously kisses and bites her, and hoists her up on his horse. He then rides to Hell, taking her with him, fulfilling her end of the deal with the Devil. Crane returns home to New York with Katrina and Young Masbath, just in time for the new century.

Question: Why does Crane start believing that the Headless Horseman is real?
Answer: He encounters the Horseman when the Horseman kills the town magistrate.
Alternative answer: He encounters the Headless Horseman