Marine archaeologists from Stockholm's Sodertorn University found finger-thick hazel rods grouped on the sea bed.
They are thought to be the remains of stationary basket traps.
"This is the world's oldest find when it comes to fishing," said Johan Ronnby, a professor in marine archaeology.
Arne Sjostrom, a fellow archaeologist who worked on the Sodertorn project, said the sticks seemed to have been used as a "sort of fence to lead the fish into a creel or they were part of the actual creel".
The remains of seven basket traps were found in a submerged ancient river valley off Sweden's southern coast at a depth of 5-12m (16.5-40ft), Mr Sjostrom said.