Despite its ubiquity and significance, behavioral habituation is poorly understood in terms of the underlying neural circuit mechanisms. Here, we present evidence that habituation arises from potentiation of inhibitory transmission within a circuit motif commonly repeated in the nervous system. In Drosophila, prior odorant exposure results in a selective reduction of response to this odorant. Both short-term (STH) and long-term (LTH) forms of olfactory habituation require function of the rutabaga-encoded adenylate cyclase in multiglomerular local interneurons (LNs) that mediate GABAergic inhibition in the antennal lobe; LTH additionally requires function of the cAMP response element-binding protein (CREB2) transcription factor in LNs. The odorant selectivity of STH and LTH is mirrored by requirement for NMDA receptors and GABA(A) receptors in odorant-selective, glomerulus-specific projection neurons(PNs). The need for the vesicular glutamate transporter in LNs indicates that a subset of these GABAergic neurons also releases glutamate. LTH is associated with a reduction of odorant-evoked calcium fluxes in PNs as well as growth of the respective odorant-responsive glomeruli. These cellular changes use similar mechanisms to those required for behavioral habituation. Taken together with the observation that enhancement of GABAergic transmission is sufficient to attenuate olfactory behavior, these data indicate that habituation arises from glomerulus-selective potentiation of inhibitory synapses in the antennal lobe. We suggest that similar circuit mechanisms may operate in other species and sensory systems.