In many synapses, depletion and recruitment of releasable synaptic vesicles contribute to use-dependent synaptic depression and recovery. Recently it has been shown that high-frequency presynaptic stimulation enhances recovery from depression, which may be mediated by Ca2+. We addressed this issue by measuring quantal release rates at the calyx of Held synapse and found that transmission is mediated by a heterogeneous population of vesicles, with one subset releasing rapidly and recovering slowly and another one releasing reluctantly and recovering rapidly. Ca2+ promotes refilling of the rapidly releasing synaptic vesicle pool and calmodulin inhibitors block this effect. We propose that calmodulin-dependent refilling supports recovery from synaptic depression during high-frequency trains in concert with rapid recovery of the slowly releasing vesicles.