Extra-pair paternity (EPP) is often linked to male age in socially monogamous vertebrates, i.e. older males are more likely to gain EPP and less likely to be cuckolded. However, whether this occurs because males improve at gaining paternity as they grow older, or because ‘higher quality’ males that live longer are preferred by females, has rarely been tested, despite being central to our understanding of the evolutionary drivers of female infidelity. Moreover, how extra-pair reproduction changes with age within females has received even less attention. Using 18 years of longitudinal data from an individually-marked population of Seychelles warblers (Acrocephalus sechellensis), we found considerable within-individual changes in extra-pair reproduction in both sexes, i.e. an early-life increase and a late-life decline. Furthermore, males were cuckolded less as they aged. Our results indicate that in this species age-related patterns of extra-pair reproduction are determined by within-individual changes with age, rather than differences among individuals in longevity.  These results challenge the hypothesis – based on longevity reflecting intrinsic quality – that the association between male age and EPP is due to females seeking high quality paternal genes for offspring. Importantly, EPP accounted for up to half of male reproductive success, emphasising the male fitness benefits of this reproductive strategy. Finally, the occurrence of post-peak declines in extra-pair reproduction provides explicit evidence of senescence in infidelity in both males and females.