Large marine predators feeding on fish caught by fishers on fishing gear, a behaviour termed “depredation”, frequently results in conflicts with significant ecological and socio-economic impacts. While adjusting fishing practices through spatio-temporal avoidance of depredation may offer an expedient and cost-effective mean of mitigating the conflict, its effectiveness is often limited by a poor understanding of the underlying drivers. Using 10 years of logbook data and generalised additive models, our study identified the environmental and operational factors influencing shark and odontocete (toothed whales) depredation on tuna catches of the New Caledonia longline fishery. Odontocete depredation was primarily driven by environmental factors such as sea surface temperature, bathymetry and sea surface height, whereas shark depredation was primarily driven by operational factors like the number of hooks set and soaking time. The findings suggest that depredation is more likely to occur in areas where predator natural distribution overlaps with fishing activities, and when fishers increase opportunities for predators to locate their gear. Targeted strategies, such as reducing soaking time to under 12 hours or limiting hooks per set to fewer than 1,750, could halve the likelihood of depredation, offering practical solutions to mitigate these interactions. Modelled predictions of the spatio-temporal patterns of depredation show well-delineated hotspots of odontocete depredation that can inform avoidance strategies developed by fishers. However, large variations in depredation probabilities among vessels suggest that additional factors related to individual fishers’ behaviours or with intrinsic features of vessels influencing their detectability need further investigation to fully understand depredation mechanisms.