Selective harvesting of animals by humans can affect the sustainability and genetics of their wild populations. Bycatch - the accidental catch of non-target species - spans the spectrum of marine fauna and constitutes a harvesting pressure. Individual differences in attraction to fishing vessels and consequent susceptibility to bycatch exist, but few studies integrate this individual heterogeneity with demography. Here, we tested for the evidence and consequences of individual heterogeneity on the demography of the wandering albatross, a seabird heavily affected by fisheries bycatch. We found strong evidence for heterogeneity in survival with one group of individuals having a 5.2% lower annual survival probability than another group, and a decrease in the proportion of those individuals with the lowest survival in the population coinciding with a 7.5 fold increase in fishing effort in the foraging areas. Potential causes for the heterogeneity in survival are discussed and we suggest that bycatch removed a large proportion of individuals attracted by fishing vessels and had significant phenotypic and population consequences.