Changing movement patterns in response to environmental perturbations is a critical aspect of gait and is related to reducing the energetic cost of the movement. Exercise improves energetic capacity for submaximal exercise and may affect how people adapt movement to reach an energetic minimum. The purpose of this study was to determine whether self-reported exercise behavior influences gait adaptation in young adults. Young adults who met the optimal volume of exercise according to the Physical Activity Guidelines for Americans (MOVE; n = 19) and young adults who did not meet the optimal volume of exercise (notMOVE; n = 13) walked on a split-belt treadmill with one belt moving twice the speed of the other belt for 10 minutes. Step length asymmetry (SLA) and mechanical work done by each leg were measured. Nonlinear mixed effects models compared the time course of adaptation between MOVE and notMOVE, and t-tests compared net work at the end of adaptation between MOVE and notMOVE. Compared to notMOVE, MOVE had a faster initial response to the split belt treadmill, and continued to adapt over the duration of split-belt treadmill walking. Young adults who engage in sufficient amounts of exercise responded more quickly to the onset of a perturbation, and throughout the perturbation they continued to explore movement strategies, which might be related to reduction of energetic cost. Our findings provide insights into the multisystem positive effects of exercise, including walking adaptation.