Many animals maintain an internal representation of their heading as they move through their surroundings. Such a compass representation was recently discovered in a neural population in the Drosophila melanogaster central complex, a brain region implicated in spatial navigation. Here, we use two-photon calcium imaging and electrophysiology in head-fixed walking flies to identify a different neural population that conjunctively encodes heading and angular velocity, and is excited selectively by turns in either the clockwise or counterclockwise direction. We show how these mirror-symmetric turn responses combine with the neurons' connectivity to the compass neurons to create an elegant mechanism for updating the fly's heading representation when the animal turns in darkness. This mechanism, which employs recurrent loops with an angular shift, bears a resemblance to those proposed in theoretical models for rodent head direction cells. Our results provide a striking example of structure matching function for a broadly relevant computation.