Sanctioned longline fishing for Patagonian toothfish around the Prince Edward Islands (a globally important seabird breeding site) commenced in 1996 following high levels of Illegal, Unregulated and Unreported (IUU) fishing. Independent fishery observers accompanied all but two sanctioned trips between 1996 and 2000, allowing a thorough excellent understanding of the impact of this fishery on seabirds. Overall, white-chinned petrels Procellaria aequinoctalis were by far the most frequently killed species. However, during the first year, when lines were set during the day and night, a significant number of albatrosses (particularly grey-headed albatrosses Thalassarche chrysocome) were also killed. Birds were caught almost exclusively during their breeding seasons and most birds killed were breeding adult males from the Prince Edward Islands. Albatrosses and giant petrels were caught almost exclusively during day sets, whereas catch rates of white-chinned petrels did not differ between day and night sets. Albatrosses were caught closer to the islands than white-chinned petrels. Most white-chinned petrel carcasses were hooked in their wings and bodies, whereas albatrosses were caught most frequently in their bills. Albatross carcasses also contained large numbers of baits, indicating that fishers may be losing significant potential revenue by allowing these birds to access baited hooks. Rates of seabird bycatch in the sanctioned fishery decreased from 0.19 birds/1000 hooks to 0.034 birds/1000 hooks during the time of this study. This was probably mainly due to stricter implementation of mitigation measures and a progressive movement farther away from the islands over the years. We estimate that the combined impact of sanctioned and IUU longline fishing around the Prince Edward Islands over the past four years, could have resulted in close to 7000 seabird mortalities and could have had significant impacts on the breeding populations of several seabird species breeding on the Prince Edward Islands. This was mainly due to high levels of IUU fishing during 1996/97.