All species face the important adaptive problem of efficiently locating high-quality nutritional resources. We explored whether human spatial cognition is enhanced for high-calorie foods, in a large multisensory experiment that covertly tested the location memory of people who navigated a maze-like food setting. We found that individuals incidentally learned and more accurately recalled locations of high-calorie foods - regardless of explicit hedonic valuations or personal familiarity with foods. In addition, the high-calorie bias in human spatial memory already became evident within a limited sensory environment, where solely odor information was available. These results suggest that human minds continue to house a cognitive system optimized for energy-efficient foraging within erratic food habitats of the past, and highlight the often underestimated capabilities of the human olfactory sense.