Humans can learn some novel movements by independently discovering the actions that lead to success. This discovery process, exploration, requires increased motor variability to determine the best movement. However, in bipedal locomotion especially, increasing motor variability decreases stability, heightening the risk of negative outcomes such as a trip, injury, or fall. Despite this stability constraint, the current study shows that individuals do use exploration to find the most rewarding walking patterns. This form of learning led to improved explicit retention but not implicit aftereffects. Thus, the reinforcement learning framework can explain findings across a wide range of motor and cognitive tasks, including locomotion.