Humans can rapidly memorize numerous images, which is surprising considering the limited visual sampling of each image. To enhance the probability of recall, it is crucial to focus on previously sampled locations most likely to support memory. How does the visuomotor system achieve this? To study this, we analyzed the eye movements of a group of neurotypical observers while they performed a natural scene memorization task. Using comprehensive gaze analysis and computational modeling, we show that observers traded off visual exploration for exploiting information at the most memorable scene locations with repeated viewing. Furthermore, both the explore-exploit trade-off and gaze consistency predicted accurate memory recall. Finally, false alarms were predicted by confusion of the incoming visual information at fixated locations with previously sampled information from other images. Together, our findings shed light on the symbiotic relationship between attention and memory in facilitating accurate natural scene memory.