We can maintain some sense of direction in the dark by keeping track of our own movements, but when visual landmarks are available, our sense of direction is more accurate and stable. Moreover, we can learn new landmarks in new environments. What mechanisms reconcile self-movement information with ever-changing landmarks to generate a coherent sense of direction? In the Drosophila brain, compass neurons form an attractor network whose activity tracks the angular position of the fly using both self-movement and visual inputs. Using whole-cell recordings and calcium imaging from Drosophila compass neurons, we show that each compass neuron is inhibited by visual cues in specific horizontal positions, with different visual maps in different individuals. Inhibition arises from GABAergic axons that form an all-to-all matrix of synaptic connections onto compass neurons. We show that visual input to the compass network can reorganize over minutes when visuo-motor correlations change in virtual reality. This reorganization causes persistent changes in the reference frame of the compass network and can depress or potentiate visually-evoked inhibition in a manner that depends on visual-heading correlations. Plasticity of sensory inputs, when combined with network attractor dynamics, should allow the brain’s spatial maps to incorporate sensory cues in new environments.