Cerebellar long-term depression (LTD) is a calcium-dependent process in which coincident activity of parallel fiber (PF) and climbing fiber (CF) synapses causes a long-lasting decrease in PF synaptic strength onto Purkinje cells. Here we show that pairing CF activation with bursts of PF activity triggers large (>10 microM) calcium signals in Purkinje cell dendrites. When PFs are densely activated, signals span whole dendritic branchlets and are mediated by voltage-dependent calcium entry. When PFs are sparsely activated, however, signals are restricted to single spines and blocked by metabotropic glutamate receptor antagonists. Single-spine signals and sparse-stimulation LTD are also blocked by thapsigargin, indicating that calcium must be released from stores. Single-spine signals and sparse-stimulation LTD are greatest when PF activation precedes the CF activation within 50-200 ms. This timing rule matches the properties of several forms of motor learning, providing a link between behavior and functional properties of cerebellar synaptic plasticity.