Many animals rely on olfactory cues to navigate their environments. For example, insects are particularly adept at locating odor sources. The navigational algorithms of insects have often been modeled as simple sensorimotor reflexes based on instantaneous cues: surging upwind when encountering the odor and casting crosswind when losing contact with the odor. To investigate whether insects rely on their past sensory experience to guide olfactory-based navigation, we developed a virtual reality olfactory set-up for Drosophila that allows precise closed-loop control over odor encounters. We found that walking flies have a strong preference to track an olfactory plume along its air-odor boundary. The flies repeatedly leave and return to the boundary, a strategy we call “edge tracking”, allowing them to advance along a plume even when it is not aligned to the wind. To uncover the computations underlying edge tracking, we developed a switching state-space model that infers the latent leaving and returning goal directions from fly trajectories. Our analyses reveal that edge tracking cannot be attributed to reflexive behaviors alone. Instead, it requires that flies maintain a memory of past entry directions to set the returning goal direction. The model predicts that the returning goal direction can be altered by a few operant training sessions in which appetitive odor is turned on whenever flies walk in a specific direction. We verified this prediction with behavioral experiments. Our model can be mapped directly onto the neural circuits of the Drosophila fan-shaped body, building the foundation for investigating underlying neural mechanisms.