In the Drosophila brain, 'compass' neurons track the orientation of the body and head (the fly's heading) during navigation 1,2. In the absence of visual cues, the compass neuron network estimates heading by integrating self-movement signals over time3,4. When a visual cue is present, the estimate of the network is more accurate1,3. Visual inputs to compass neurons are thought to originate from inhibitory neurons called R neurons (also known as ring neurons); the receptive fields of R neurons tile visual space5. The axon of each R neuron overlaps with the dendrites of every compass neuron6, raising the question of how visual cues are integrated into the compass. Here, using in vivo whole-cell recordings, we show that a visual cue can evoke synaptic inhibition in compass neurons and that R neurons mediate this inhibition. Each compass neuron is inhibited only by specific visual cue positions, indicating that many potential connections from R neurons onto compass neurons are actually weak or silent. We also show that the pattern of visually evoked inhibition can reorganize over minutes as the fly explores an altered virtual-reality environment. Using ensemble calcium imaging, we demonstrate that this reorganization causes persistent changes in the compass coordinate frame. Taken together, our data suggest a model in which correlated pre- and postsynaptic activity triggers associative long-term synaptic depression of visually evoked inhibition in compass neurons. Our findings provide evidence for the theoretical proposal that associative plasticity of sensory inputs, when combined with attractor dynamics, can reconcile self-movement information with changing external cues to generate a coherent sense of direction7-12.