Long-line fishing mortality poses a significant threat to many large procellariiform seabirds. To date, estimates of impacts have concentrated on lower survival rates, largely ignoring the costs to fecundity resulting from disruption of breeding pairs and skews in sex ratio. A comparative, stochastic, individual-based model was used to investigate these costs for the wandering albatross Diomedea exulans. Ignoring the time taken to replace a lost mate overestimates fecundity by 13–18%, resulting in annual population growth rates (λ) being 0.006–0.007 too high. Long-line mortality exacerbates this cost, which becomes more substantial with increasing demographic skew resulting from female-biased mortality. At moderate levels of long-line mortality (2–4% per year), 80% female-biased mortality reduces fecundity by 9–27% and λ by 0.003–0.010 relative to models with random mortality. Biased sex ratios accumulate and, unlike reduced survival, their impacts on albatross demography persist after long-line mortality ceases. Estimates of the demographic costs of long-line mortality should incorporate individual-level effects, especially where mortality is sex-biased.