Learning to perform a behavioural procedure as a well-ingrained habit requires extensive repetition of the behavioural sequence, and learning not to perform such behaviours is notoriously difficult. Yet regaining a habit can occur quickly, with even one or a few exposures to cues previously triggering the behaviour. To identify neural mechanisms that might underlie such learning dynamics, we made long-term recordings from multiple neurons in the sensorimotor striatum, a basal ganglia structure implicated in habit formation, in rats successively trained on a reward-based procedural task, given extinction training and then given reacquisition training. The spike activity of striatal output neurons, nodal points in cortico-basal ganglia circuits, changed markedly across multiple dimensions during each of these phases of learning. First, new patterns of task-related ensemble firing successively formed, reversed and then re-emerged. Second, task-irrelevant firing was suppressed, then rebounded, and then was suppressed again. These changing spike activity patterns were highly correlated with changes in behavioural performance. We propose that these changes in task representation in cortico-basal ganglia circuits represent neural equivalents of the explore-exploit behaviour characteristic of habit learning.