Flexibility is a hallmark of memories that depend on the hippocampus. For navigating animals, flexibility is necessitated by environmental changes such as blocked paths and extinguished food sources. To better understand the neural basis of this flexibility, we recorded hippocampal replays in a spatial memory task where barriers as well as goals were moved between sessions to see whether replays could adapt to new spatial and reward contingencies. Strikingly, replays consistently depicted new goal-directed trajectories around each new barrier configuration and largely avoided barrier violations. Barrier-respecting replays were learned rapidly and did not rely on place cell remapping. These data distinguish sharply between place field responses, which were largely stable and remained tied to sensory cues, and replays, which changed flexibly to reflect the learned contingencies in the environment and suggest sequenced activations such as replay to be an important link between the hippocampus and flexible memory.