Jerimalai Cave in East Timor contains the oldest evidence of occupation by modern humans on the islands that were the stepping stones from South-East Asia to Australia. In 2011 Sue O'Connor and colleagues from the Australian National University in Canberra found two broken fish hooks made from shells at Jerimalai cave. The hooks, which dated between 21,000 and 16,000 BCE are the earliest fish hooks known.
"The team also found more than 38,000 fish bones at the site, dating the oldest back to 42,000 years ago. Some were from inshore species, but almost half were from 'pelagic species' — fish that dwell in the open ocean, providing the oldest known evidence of humans fishing far from shore. The most commonly found pelagic species at the site were Tuna, but there was also evidence of humans eating sharks and rays, among others.
“ 'That these types of fish were being routinely caught 40,000 years ago is extraordinary,' says O'Connor. 'It requires complex technology and shows that early modern humans in island South East Asia had amazingly advanced maritime skills.' "
"Far older fish bones have been found at sites in southern Africa – those at the Blombos Cave in South Africa, for example, date from 140,000–50,000 years ago – but they have generally been from inshore species whose capture would require less complex technology2. A small number of tuna vertebrae have been found, but these can be attributed to scavenging of fish washed up on beaches, says Richard Klein, an archaeologist at Stanford University in California, who has worked extensively in the region. The oldest known fishing tackle from the vicinity dates from around 12,000 years ago, but it includes only bone gorges (straight hooks) and net sinkers, probably used exclusively inshore, he adds" (http://www.nature.com/news/archaeologists-land-world-s-oldest-fish-hook-1.9461#b1, accessed 01-18-2013).