One of the earliest signs of advanced maritime skill, deep-sea fishing has been tenuously traced back roughly 12,000 years. Now an archaeologist has lengthened that timeline another 30,000 years.

The researcher, Sue O’Connor of Australian National University, began her search on an island off the northern coast of Australia where colonizers from Asia are thought to have landed. O’Connor had already found early fishing technology in the area, so when local hunters led her to a nearby limestone cave, she wondered whether it had once sheltered ancient mariners.

To find out, she hired a team of farmers and started digging. One month later they had recovered some 10,000 bits of stone, bone, and shell. The deepest, oldest layers of sediment had hardened, yielding chunks with artifacts studding their surfaces. It was impossible to know what was inside.

O’Connor brought the slabs to her lab and treated them with acetic acid, which coaxed out thousands more fish bones. Many of the oldest belonged to tuna, sharks, and other fast, deep-swimming fish that could not have been brought to the cave without boats and sophisticated equipment. O’Connor was startled to find that these remains dated to 42,000 years ago, the earliest evidence of deep-sea fishermen on record: “We knew we had a really big fishing story.”