Depredation is a human–wildlife interaction over access to resources, which often includes a combination of socio-economic, ecological and conservation issues. However, estimating the amount of resource depredated can be especially challenging when depredation occurs on fish in the marine environment. This is the case for killer whales (Orcinus orca) and sperm whales (Physeter macrocephalus) depredation on the demersal Patagonian toothfish (Dissostichus eleginoides) longline fishery operating within the Crozet Islands EEZ (southern Indian Ocean). This study aimed at providing two indirect methods of assessment of depredated biomass over an 11-year period (2003 to 2013), accounting for spatial variations of depredation levels. In the first method, fishing data from 6 525 longline sets were used to calculate the difference between catch-per-unit-effort (CPUE) of non-depredated and depredated lines. When killer whales and sperm whales occurred separately, 575 ± 35 tonnes and 739 ± 87 tonnes of Patagonian toothfish respectively were estimated to be depredated by the two species. When the two species co-occurred around vessels, 1 679 ± 74 tonnes were depredated. The second method used the differences in the proportion of grenadiers (Macrourus spp.) between non-depredated and depredated longline sets to estimate the number of depredated Patagonian toothfish. This approach, which can only be implemented when a sufficient level of by-catch species occurs, provides comparable results and thus strong support for the CPUE method. From these two methods, depredation rates were estimated to range from 27.3% to 29.1% of the total catch (landed and depredated), which is one of the highest among all similar situations where depredation is reported elsewhere in the world. In addition to providing a methodology that could be used in other areas with depredation issues, these findings emphasise the critical importance for fishery managers and researchers to account for depredation when assessing fish stocks, fishery economics and/or conservation of odontocetes.