Some genes are essential for survival, while other genes play modulatory roles on health and survival. Genes that play modulatory roles may promote an organism’s survival and health by fine-tuning physiological processes. An unbiased search for genes that alter an organism’s ability to maintain aspects of health may uncover modulators of lifespan and healthspan. From an unbiased screen for Caenorhabditis elegans mutants that show a progressive decline in motility, we aimed to identify genes that play a modulatory role in maintenance of locomotor healthspan. Here we report the involvement of hda-3, encoding a class I histone deacetylase, as a genetic factor that contributes in the maintenance of general health and locomotion in C. elegans. We identified a missense mutation in HDA-3 as the causative mutation in one of the isolated strains that show a progressive decline in maximum velocity and travel distance. From transcriptome analysis, we found a cluster of genes on Chromosome II carrying BATH domains that were downregulated by hda-3. Furthermore, downregulation of individual bath genes leads to significant decline in motility. Our study identifies genetic factors that modulate the maintenance of locomotor healthspan and may reveal potential targets for delaying age-related locomotor decline.