Explaining variation in individual fitness is a key goal in evolutionary biology. Recently, telomeres, repeating DNA sequences capping chromosome ends, have gained attention as a biomarker for body state, physiological costs, and senescence. Existing research has provided mixed evidence for whether telomere length correlates with fitness, including survival and reproductive output. Moreover, few studies have examined how the rate of change in telomere length correlates with fitness in wild populations. Here, we intensively monitored an insular population of house sparrows, and collected longitudinal telomere and life history data (16 years, 1225 individuals). We tested whether telomere length and its rate of change predict fitness measures, namely survival, lifespan and annual and lifetime reproductive effort and success. Telomere length positively predicted short-term survival, independent of age, but did not predict lifespan, suggesting either a diminishing telomere length-survival correlation with age or other extrinsic factors of mortality. The positive association of telomere length with survival translated into reproductive benefits, as birds with longer telomeres produced more genetic recruits, hatchlings and reared more fledglings over their lifetime. In contrast, there was no association between telomere dynamics and annual reproductive output, suggesting telomere dynamics might not reflect the costs of reproduction in this population, potentially masked by variation in individual quality. The rate of change of telomere length did not correlate with neither lifespan nor lifetime reproductive success. Our results provide further evidence that telomere length correlates with fitness, and contribute to our understanding of the selection on, and evolution of, telomere dynamics.