Average telomere length (TL) in blood cells has been shown to decline with age in a range of vertebrate species, and there is evidence that TL is a heritable trait associated with late-life health and mortality in humans. In non-human mammals, few studies to date have examined lifelong telomere dynamics and no study has estimated the heritability of TL, despite these being important steps towards assessing the potential of TL as a biomarker of productive lifespan and health in livestock species. Here we measured relative leukocyte TL (RLTL) in 1,328 samples from 308 Holstein Friesian dairy cows and in 284 samples from 38 female calves. We found that RLTL declines after birth but remains relatively stable in adult life. We also calculated the first heritability estimates of RLTL in a livestock species which were 0.38 (SE = 0.03) and 0.32 (SE = 0.08) for the cow and the calf dataset, respectively. RLTL measured at the ages of one and five years were positively correlated with productive lifespan (p < 0.05). We conclude that bovine RLTL is a heritable trait, and its association with productive lifespan may be used in breeding programmes aiming to enhance cow longevity.