1. Seabirds have been incidentally caught in distant-water longline fleets operating in the Southern Ocean since at least the 1970s, and breeding numbers for some populations have shown marked trends of decline and recovery concomitant with longline fishing effort within their distributions. However, lacking is an understanding of how forms of among-individual heterogeneity may interact with fisheries bycatch and influence population dynamics. 2. We develop a model that uses comprehensive data on the spatial and temporal distributions of fishing effort and seabird foraging to estimate temporal overlaps, fishery catchability and consequent bycatch. We apply a population model that is structured by age, sex, life stage and spatially to Crozet Island wandering albatross and explore how heterogeneity in susceptibility to capture may have influenced the population's demography over time. 3. A model where some birds were assumed to be more susceptible to fisheries bycatch was able to successfully replicate the observed trend in breeding pairs. Considerably poorer fits were found without this assumption. Results suggested that the more susceptible birds may have been removed from the population by the 1990s. 4. The model was also able to highlight areas, times and fleets prone to increased bycatch. Knowledge of these factors should assist fisheries and conservation management bodies to quantify and reduce seabird bycatch through spatial management and fleet-specific mitigation efforts. 5. Synthesis and application. Many seabirds show complex life histories that make them highly susceptible to additional incidental mortality from fishing vessels. By applying a population model that integrates key aspects of seabird and fishery dynamics, we were able to explain the observed trends in the breeding population of Crozet wandering albatross and identify key areas and fleets where further mitigation may be required. In addition, the potential removal of a category of birds that shows increased susceptibility to capture has important implications for the conservation management of this population and other iconic species incidentally caught by large-scale commercial fisheries.