Environmental context can have a profound influence on the efficacy of intervention protocols designed to eliminate undesirable behaviors. This is clearly seen in drug rehabilitation clinics where patients often relapse soon after leaving the context of the treatment facility. A similar pattern is commonly observed in controlled laboratory studies of context-dependent savings in instrumental conditioning, where simply placing an animal back into the original conditioning chamber can renew an extinguished instrumental response. Surprisingly, context-dependent savings in human procedural learning has not been carefully examined in the laboratory. Here, we provide the first known empirical demonstration of context-dependent savings in a perceptual categorization task known to recruit procedural learning. We also present a computational account of these savings using a biologically detailed model in which a key role is played by cholinergic interneurons in the striatum.