Humans are capable of learning many new walking patterns. People have learned to snowshoe up mountains, racewalk marathons, and march in precise synchrony. But what is required to learn a new walking pattern? Here, we demonstrate that people can learn new walking patterns without actually walking. Through a series of experiments, we observe that stepping with only one leg can facilitate learning of an entirely new walking pattern (i.e., split-belt treadmill walking). We find that the nervous system learns from the relative speed difference between the legs-whether or not both legs are moving-and can transfer this learning to novel gaits. We also show that locomotor learning requires active movement: observing another person adapt their gait did not result in significantly faster learning. These findings reveal that people can learn new walking patterns without bilateral gait training, as stepping with one leg can facilitate adaptive learning that transfers to novel gait patterns.