According to police records, shortly after Lucas and Toole met, they spent their "leisure time," drinking and cruising the highways looking for "fun." Apparently, their idea of fun was to rob small convenience stores and, on the odd occasion, banks. They stole money, food and beer and took obvious delight in terrorizing the staff.

The pair became bolder and more violent with every crime. Eventually their crimes became more brutal, to the point where, if a store clerk or bank teller resisted in the slightest way, they were gunned down and left in a pool of blood. Lucas would later relate one such incident to the Georgia Bureau of Investigation.

Henry Lee Lucas

He told police that he and Ottis robbed a small convenience store in western Georgia. Lucas walked to the front counter and produced a .22 calibre handgun and held it to the temple of the female clerk. After binding the terrified woman with rope, he dragged her to the back of the store while Toole rifled the till. The woman began to scream and struggle to get loose. Lucas told her, "I you don’t keep quiet, I’m gonna have to shoot ya." Fearing for her life, the woman obeyed. As they were dividing the money, Lucas noticed that the woman was trying to loosen the ropes. Casually he walked to the back of the store and shot her through the temple. Afterwards, while Henry loaded cases of beer into their car, Toole had sex with the woman’s body. At the conclusion of the admission, Lucas told police, "Now see, that’s the difference between me and Ottis. He just kills ‘em when he feels like it. At least I warn ‘em first."

What disturbed the investigators most was that Lucas told the story without any emotion or remorse, as though he were describing an incident that someone else was responsible for.

The killing continued to escalate as the murderous pair seized every opportunity to commit more and more brutal crimes. They seemed to be driven by the desire to prove who was the more lethal. Toole later bragged to police of one such incident. While cruising the I-35 highway through Texas, they came across a teenage couple walking alongside the road. Apparently the couple’s car had run out of gas and they were on their way to a local filling station. Ottis stepped out of the vehicle and shot the boy nine times in the head and chest and rolled the body into a culvert while Lucas dragged the hysterical girl into the back seat. While Ottis drove, Henry raped the girl repeatedly. Ottis explained that watching Lucas having sex with someone else made him angry. Seething with jealous rage, Toole then stopped the car and, dragging the girl onto the roadway, shot her six times. They then drove back towards Jacksonville leaving the body lying on the road.

Everyone they came in contact with was a potential victim. Drifters, women with car troubles and hitchhikers, all fell prey to the deadly duo. Because the murders were mostly committed in remote areas, there were no witnesses. If their cars broke down or ran out of gas, they would steal another, usually murdering the driver. They would then drive the new vehicle to another state, dump it and hitchhike to the next location.

When they weren’t robbing, raping and killing, they would work odd jobs until the urge for blood became too strong and they continued their odyssey of destruction.

The killing was to continue, even when the pair later travelled with Frank and "Becky" Powell, who by that time had become Henry’s lover. She was just twelve years old. From Maryland to California, Texas to Michigan, they raped, robbed and murdered. Often, while Frank and Becky waited in the car, the two men would commit their crimes and drive off as though nothing unusual had occurred. Henry said he particularly enjoyed killing women whose cars had broken down on lonely roads. He told police he considered them, "free lunch."

One such victim was found dumped in a field, completely nude. She had been stabbed thirty-five times in the chest, neck, arms and back. Deep cuts had been made along the inside of her arms and from the middle of her chest to the pubic bone. Both nipples had been cut off and removed. According to police, who methodically pieced together the killer’s trail of terror from pay-slips and discarded vehicles, Ottis and Toole were responsible for up to four or five murders in each state before moving across state lines to avoid detection. On more than two occasions, the pair committed several murders in a single day.