Abstract Background Gait speed is a powerful indicator of health with aging. Potential genetic contributions to gait speed and its decline with aging are not well defined. We determined the heritability of and potential genetic regions underlying change in gait speed using longitudinal data from 2379 individuals belonging to 509 families in the Long Life Family Study (mean age 64 ± 12, range 30–110 years; 45% men). Methods Gait speed was measured over 4 m at baseline and follow-up (7 ± 1 years). Quantitative trait linkage analyses were completed using pedigree-based maximum likelihood methods with logarithm of the odds (LOD) scores greater than 3.0, indicating genome-wide significance. We also performed linkage analysis in the top 10% of families contributing to LOD scores to allow for heterogeneity among families (HLOD). Data were adjusted for age, sex, height, and field center. Results At baseline, 26.9% of individuals had “slow” gait speed less than 1.0 m/s (mean: 1.1 ± 0.2 m/s) and gait speed declined at a rate of −0.02 ± 0.03 m/s per year (p < .0001). Baseline and change in gait speed were significantly heritable (h2 = 0.24–0.32, p < .05). We did not find significant evidence for linkage for baseline gait speed; however, we identified a significant locus for change in gait speed on chromosome 16p (LOD = 4.2). A subset of 21 families contributed to this linkage peak (HLOD = 6.83). Association analyses on chromosome 16 showed that the strongest variant resides within the ADCY9 gene. Conclusion Further analysis of the chromosome 16 region, and ADCY9 gene, may yield new insight on the biology of mobility decline with aging.