Within the Crozet Islands Exclusive Economic Zone (EEZ), the Patagonian toothfish longline fishery is exposed to high levels of depredation by killer and sperm whales. In this context, this study (i) provides estimations of annual depredation levels on a 5-years period (2003-2008), (ii) proposes operational measures to reduce depredation levels using the current longline fishing technique. From 2003 to 2008, sperm whales alone, killer whales alone, and the two species co-occurring were observed on respectively 32.6%, 18.6% and 23.4% of the 4289 lines hauled out over this period. Over this 5 year period we estimated a total loss of 1200 tons of Patagonian toothfish due to depredation which represents a financial loss of approximately 10 millions €. Killer whales were found to be responsible for the largest part of this loss (70%) while sperm whales had a lower impact (30%). Photo-identification data revealed that among the 97 killer whales interacting with the fishery, however 35 individuals belonging to four different pods were involved in 81.3% of the interaction events. We also estimated that a total of 64 sperm whales interacted with the fishery on the Crozet EEZ in 2008. Significant variations of interaction rates with killer whales were detected between vessels suggesting the influence of operational factors on depredation. When killer whales were absent at the beginning of the line hauling process, short lines (<5000m) provided higher yield and were significantly less impacted by killer whales than longer lines. No differences were found if killer whales were present when hauling started. Based on the analyse of killer whales movements in relation to fishing vessel, when facing depredation we recommend vessels to leave their fishing area and travel on distances greater than 40Nm to prevent killer whales from finding them within few hours. More data are still needed to better understand how killer whales search and detect fishing vessels. In a way to suppress cetacean depredation fish traps will be tested on an experimental campaign which will take place in early 2010.