During odor sensing the activity of principal neurons of the mammalian olfactory bulb, the mitral and tufted cells (MTCs), occurs in repetitive bursts that are synchronized to respiration, reminiscent of hippocampal theta-gamma coupling. Axonless granule cells (GCs) mediate self- and lateral inhibitory interactions between the excitatory MTCs via reciprocal dendrodendritic synapses. We have explored long-term plasticity at this synapse by using a theta burst stimulation (TBS) protocol and variations thereof. GCs were excited via glomerular stimulation in acute brain slices. We find that TBS induces exclusively long-term depression in the majority of experiments, whereas single bursts ("single-sniff paradigm") can elicit both long-term potentiation and depression. Statistical analysis predicts that the mechanism underlying this bidirectional plasticity involves the proportional addition or removal of presynaptic release sites. Gamma stimulation with the same number of APs as in TBS was less efficient in inducing plasticity. Both TBS- and "single-sniff paradigm"-induced plasticity depend on NMDA receptor activation. Since the onset of plasticity is very rapid and requires little extra activity, we propose that these forms of plasticity might play a role already during an ongoing search for odor sources. Our results imply that components of both short-term and long-term olfactory memory may be encoded at this synapse.