Hidden in the coral terraces that line the eastern shores of East Timor are troves of artifacts and skeletal remains that tell a story of coastal activity going back tens of thousands of years — to the time when humans first settled nearby Australia.

Recently, in a terrace cave called Jerimalai, a team of archaeologists discovered pieces of what are now the oldest known fishhooks in the world — dating from 16,000 to 23,000 years ago and made of shell. While these old samples are too incomplete to reveal exactly how they were used, the team also found fishhooks that are more intact from 11,000 years ago. These newer ones are classic baited jabbing fishhooks: They were most likely tied to a line, loaded with bait and thrown into the water.

The archaeologists, whose findings appear in Science, also uncovered 42,000-year-old fish remains, including bones from tuna, which live only in deep water....