Many animals rely on an internal heading representation when navigating in varied environments 1– 10 . How this representation is linked to the sensory cues defining different surroundings is unclear. In the fly brain, heading is represented by ‘compass neurons’ that innervate a ring-shaped structure, the ellipsoid body 3, 11, 12 . Each compass neuron receives inputs from visual-feature-selective ‘ring neurons’ 13– 16 , providing the ideal substrate for the extraction of directional information from a visual scene. We combine two-photon calcium imaging and optogenetics in tethered flying flies with circuit modeling to show how the correlated activity of compass and visual neurons drives plasticity 17– 22 , that flexibly transforms two-dimensional visual cues into a stable heading representation. We also describe how this plasticity enables the fly to convert a partial heading representation established from orienting within part of a novel setting into a complete heading representation. Our results provide mechanistic insight into memory-related computations essential for flexible navigation in varied surroundings.