Interplay between dopaminergic and cholinergic neuromodulation in the striatum is crucial for movement control, with prominent models proposing pro-kinetic and anti-kinetic effects of dopamine and acetylcholine release, respectively. However, the natural, movement-related signals of striatum cholinergic neurons and their relationship to simultaneous variations in dopamine signaling are unknown. Here, functional optical recordings in mice were used to establish rapid cholinergic signals in dorsal striatum during spontaneous movements. Bursts across the cholinergic population occurred at transitions between movement states and were marked by widespread network synchronization which diminished during sustained locomotion. Simultaneous cholinergic and dopaminergic recordings revealed distinct but coordinated sub-second signals, suggesting a new model where cholinergic population synchrony signals rapid changes in movement states while dopamine signals the drive to enact or sustain those states.