Humans remember the past and use that information to plan future actions. Lab experiments that test memory for the location of food show that animals have a similar capability to act in anticipation of future needs, but less work has been done on animals foraging in the wild. We hypothesized that planning abilities are critical and common in breath-hold divers who adjust each dive to forage on prey varying in quality, location and predictability within constraints of limited oxygen availability. We equipped Risso's dolphins with sound-and-motion recording tags to reveal where they focus their attention through their externally observable echolocation and how they fine tune search strategies in response to expected and observed prey distribution. The information from the dolphins was integrated with synoptic prey data obtained from echosounders on an underwater vehicle. At the start of the dives, whales adjusted their echolocation inspection ranges in ways that suggest planning to forage at a particular depth. Once entering a productive prey layer, dolphins reduced their search range comparable to the scale of patches within the layer, suggesting that they were using echolocation to select prey within the patch. On ascent, their search range increased, indicating that they decided to stop foraging within that layer and started searching for prey in shallower layers. Information about prey, learned throughout the dive, was used to plan foraging in the next dive. Our results demonstrate that planning for future dives is modulated by spatial memory derived from multi-modal prey sampling (echoic, visual and capture) during earlier dives.