Octopodoidea are a highly versatile and diverse group of marine predators comprising > 200 species today, but their diversity and ecology in deep time are virtually unknown. Because these soft-bodied cephalopods have a low preservation potential, only a single body fossil species has been documented. Unlike other modern cephalopods, octopodoids leave behind a characteristic drill hole on their molluscan and crustacean prey. These traces provide a means to track their presence and behavior in deep time. Although severely understudied, some of such holes have been documented from the Eocene–Pleistocene fossil record. We document the oldest recognized drill holes attributed to octopodoids, found in lucinid bivalves from the Late Cretaceous (Campanian) of South Dakota, USA. These observations demonstrate that the drilling habit of these animals evolved early in the evolutionary history of Octopodoidea, ~25 million years earlier than was previously known. The drilled lucinids lived in cold methane seeps in the Western Interior Seaway. These predation traces have never been found in fossil seeps previously, thus adding a new predator to the food web of cold seeps. Finally, our results provide direct evidence that Octopodoidea were an integral component of the rise of shell-destroying predators during the Mesozoic Marine Revolution. Read the press release here.