Valentine "Val" McKee and Earl Basset work as handymen in Perfection, Nevada, an isolated ex-mining settlement in the high desert east of the Sierra Nevada mountains. They eventually tire of their jobs and leave for Bixby, the nearest town. As they leave, they discover another resident, Edgar Deems, dead on top of an electrical tower, though still holding onto the tower's crossbeams, along with his .30-30 Winchester rifle. Jim Wallace, the town doctor, determines that Edgar died of dehydration, apparently afraid for some reason to climb down.
Later on, an unknown force kills shepherd Old Fred and his flock of sheep. Upon discovering his severed head buried in the sand, Val and Earl become convinced that a killer is on the loose; they head back to town to warn the other residents. Two construction workers who ignore Val and Earl's warning are killed by the same force, causing a rockslide.
Val and Earl try to get help, but find that the phone lines are dead, and the only road out of town is completely blocked by a rockslide. Unbeknownst to them, a snake-like creature wraps itself around the truck's rear axle; the creature is torn apart when Val stomps on the gas pedal and drives away.
Val and Earl return to town and borrow horses. They come upon Wallace and his wife's buried station wagon near their trailer, but the couple is missing. As they press on, something suddenly erupts out of the ground, revealing the snake-like creature to be one of multiple tentacled "tongues" employed by an enormous burrowing worm-like creature, later named a "Graboid". Thrown from their horses, the two men run for their lives. The chase ends when the eyeless creature violently rams itself into the concrete wall of an aqueduct and dies from the impact. Rhonda LeBeck, a graduate student conducting seismology tests in the area, stumbles onto the scene; she deduces from previous soundings that there are three other Graboids in the area. Rhonda, Val, and Earl become trapped overnight atop a cluster of boulders near one of the creatures, and they eventually escape by pole vaulting from boulder to boulder to reach Rhonda's truck.
After the people return to town, the Graboids attack, eventually killing general store owner Walter Chang and forcing the other citizens to the town's rooftops. Meanwhile, nearby survivalist couple Burt and Heather Gummer manage to kill another one of the creatures after unknowingly luring it from town to their basement armory. In town, the two remaining Graboids attack the building foundations, knocking over the trailer of a citizen named Nestor and dragging him under. Realizing they cannot stay any longer, Val commandeers a bulldozer and chains a partial truck trailer to the rear, while everyone else distracts the creatures; the survivors use it to try and escape to a nearby mountain range. On the way there, both Graboids create an underground sinkhole trap that disables the bulldozer, forcing the survivors to flee to the safety of large boulders.
Earl has an idea to lure in the creatures, then to trick them into swallowing Burt's homemade pipe bombs. While this works on one Graboid, the other spits it back towards the survivors, forcing Val, Earl, and Rhonda to leave the rock to avoid the explosion. With one last pipe bomb, Val allows the creature to chase him to the edge of a cliff and then explodes the bomb behind it, frightening the Graboid into tunneling through the cliff face, where it plummets to its death. The group returns to town, where they call in the authorities to begin an investigation, and Earl pushes Val into approaching Rhonda romantically.

Question: When do Val and Earl decide there is a killer on the loose?
Answer: After finding the severed head of Old Fred.
Alternative answer: After finding old Fred dead.