Mitigating the adverse affects of commercial fishing on the environment is an integral responsibility of fisheries globally. Efforts to reduce bycatch, to exploit previously unfavourable species and to carry out research on associated organisms have increased with time but charismatic megafauna tend to gain priority, despite their numbers being relatively low compared to fish bycatch species. The Commission for the Conservation of Antarctic Marine Living Resources (CCAMLR) is widely recognized for its thorough and effective management of Southern Ocean toothfish fisheries, especially in eliminating incidental seabird mortality, but comparatively little research has been applied to the thousands of fish caught as bycatch annually. Fish bycatch mitigation controls in toothfish fisheries have seen a relatively recent evolution through CCAMLR’s conservation measures but their effectiveness has not been thoroughly investigated. This study explores trends in fish bycatch of exploratory fisheries for toothfish within the CCAMRL Convention Area, from 2006–2013, relating observations to CCAMLR’s conservation measures. We found a significant reduction in bycatch landings by weight and number of individuals across years, despite no significant reduction in fishing effort probably linked to changes in landings of skates. Bycatch by weight formed 6.7% of total catch per year, however the number of individuals landed was at times double that of toothfish. Gear type comparisons indicate that autolines catch a greater diversity of bycatch species than Spanish lines and trotlines.