Research has shown that retrieval of learned information is better when the original learning context is reinstated during testing than when this context is changed. Recently, such contextual dependencies have also been found for perceptual-motor behavior. The current study investigated the nature of context-dependent learning in the discrete sequence production task, and in addition examined whether the amount of practice affects the extent to which sequences are sensitive to contextual alterations. It was found that changing contextual cues—but not the removal of such cues—had a detrimental effect on performance. Moreover, this effect was observed only after limited practice, but not after extensive practice. Our findings support the notion of a novel type of context-dependent learning during initial motor skill acquisition and demonstrate that this context-dependence reduces with practice. It is proposed that a gradual development with practice from stimulus-driven to representation-driven sequence execution underlies this practice effect.