Adaptation is an error-driven motor learning process that can account for predictable changes in the environment (e.g., walking on ice) or in ourselves (e.g., injury). Our ability to recall and build upon adapted motor patterns across days is essential to this learning process. We investigated how different training paradigms affect the day-to-day memory of an adapted walking pattern. Healthy human adults walked on a split-belt treadmill, and returned the following day to assess recall, relearning rate, and performance. In the first experiment, one group adapted and de-adapted (i.e., washed-out the learning) several times on day 1 to practice the initial stage of learning where errors are large; another group adapted only one time and then practiced in the adapted (“learned”) state where errors were small. On day 2, they performed washout trials before readapting. The group that repeatedly practiced the initial portion of adaptation where errors are large showed the fastest relearning on the second day. In fact, the memory was nearly as strong as that of a third group that was left overnight in the adapted state and was not washed-out before reexposure on the second day. This demonstrates that alternating exposures to early adaptation and washout can enhance readaptation. In the second experiment, we tested whether the opposite split-belt pattern interferes with day 2 relearning. Surprisingly, it did not, and instead was similar to practicing in the adapted state. These results show that the structure of the initial phase of learning influences the ease of motor relearning.