Numerous studies have shown that cerebellar function is related to the plasticity at the synapses between parallel fibers and Purkinje cells. How specific input patterns determine plasticity outcomes, as well as the biophysics underlying plasticity of these synapses, remain unclear. Here, we characterize the patterns of activity that lead to postsynaptically expressed LTP using both in vivo and in vitro experiments. Similar to the requirements of LTD, we find that high-frequency bursts are necessary to trigger LTP and that this burst-dependent plasticity depends on presynaptic NMDA receptors and nitric oxide (NO) signaling. We provide direct evidence for calcium entry through presynaptic NMDA receptors in a subpopulation of parallel fiber varicosities. Finally, we develop and experimentally verify a mechanistic plasticity model based on NO and calcium signaling. The model reproduces plasticity outcomes from data and predicts the effect of arbitrary patterns of synaptic inputs on Purkinje cells, thereby providing a unified description of plasticity.