Parasites are a major component of all animal populations. However, males and females often differ in their levels of parasite prevalence potentially leading to sex differences in the impact of parasitism on host fitness. Recent theoretical work has highlighted the important implications this can have for the rapid evolution of both parasite and host traits including host resistance, tolerance and parasite virulence. However, quantitative measures of the impact of parasitism under free-living conditions are extremely rare, as they require a combination of detailed demographic data with different measures of parasite burden both within and between individuals over time. Here we use endoscopy to allow direct quantification of natural parasite burdens to match to corresponding levels of reproductive success over a seven year period in a wild population of seabirds. In contrast to what might be predicted, only female burdens were associated with negative impacts of parasitism on breeding success, despite males have significantly higher burdens than females. Female reproductive success declined by 30% across the range of natural parasite burdens. These effects persisted when accounting for inter-annual population differences in breeding success. Our results therefore provide both evidence for the existence of, and quantitative estimates of the magnitude of, profound sub-lethal effects of parasitism acting through male and female components of the population More importantly, they highlight how parasites may act in unpredicted ways to shape how ecological and evolutionary processes act in different components of the same population, with complex implications for demography and selection on host and parasite traits.