Coevolution of the gut microbiome with the host has resulted in the microbiome influencing host physiology and even behavior. Previous research shows the gut microbiome can affect exercise ability, but possible effects on physical activity are unknown. Here, we show that elimination of the gut microbiome via antibiotic treatment can reduce voluntary exercise in mice, but only in lines that have been selectively bred for high voluntary wheel running. We studied females from a unique artificial selection experiment in which 4 replicate High Runner (HR) lines are bred for voluntary wheel running and compared with 4 non-selected control (C) lines. HR differ from C in several traits that likely interact with the gut microbiome, including ~3 fold higher daily running distance, higher body temperatures when running, higher spontaneous physical activity when housed without wheels, and higher food consumption. After two weeks of wheel access to reach a stable plateau in daily running, mice were administered broad-spectrum antibiotics in their water for 10 days. Antibiotic treatment caused a significant reduction in wheel running in the HR mice (-21%) but not in the C mice. Antibiotic treatment did not reduce food consumption or body mass in either HR or C mice, suggesting that neither linetype became sick. These results indicate that gut microbes play a role in voluntary exercise and provide evidence for the coevolution of the HR mice with their gut microbiome. NSF DEB-1655362 to TG and R35GM124724 to AH.