Fisheries can generate feeding opportunities for large marine predators in the form of discards or accessible catch. How the use of this anthropogenic food may spread as a new behaviour, across individuals within populations over time, is poorly understood. This study used a 16-year (2003-2018) monitoring of two killer whale Orcinus orca subantarctic populations (regular and Type-D at Crozet), and Bayesian multistate capture-mark-recapture models, to assess temporal changes in the number of individuals feeding on fish caught on hooks ('depredation' behaviour) of a fishery started in 1996. For both populations, the number of depredating individuals increased during the study period (34 to 94 for regular; 17 to 43 for Type-D). Increasing abundance is unlikely to account for this and, rather, the results suggest depredation was acquired by increasing numbers of existing individuals. For regular killer whales, a plateau reached from 2014 suggests that it took 18 years for the behaviour to spread across the whole population. A more recent plateau was apparent for Type-Ds but additional years are needed to confirm this. These findings show how changes in prey availability caused by human activities lead to rapid, yet progressive, innovations in killer whales, likely altering the ecological role of this top-predator.