Abstract: Human activities generate food attracting many animals worldwide, causing major conservation issues. The spatio-temporal predictability of anthropogenic resources could reduce search costs for animals and mediate their attractiveness. We investigated this through GPS tracking in breeding black-browed albatrosses attracted to fishing boats. We tested for answers to the following questions. (i) Can future boat locations be anticipated from cues available to birds? (ii) Are birds able to appropriately use these cues to increase encounters? (iii) How frequently do birds use these cues? Boats were spatially persistent: birds searching in the direction where they previously attended boats would encounter twice as many boats compared with following a random direction strategy. A large proportion of birds did not use this cue: across pairs of consecutive trips (n = 85), 51% of birds switched their foraging direction irrespective of previous boat encounters. Still, 15 birds (27%) were observed to closely approach (approx. 0.1–1 km) where they previously attended a boat while boats were no longer there. This is less than the distance expected by chance (approx. 10–100 km), based on permutation control procedures accounting for individual-specific spatial consistency, suggesting individuals could memorize where they encountered boats across consecutive trips. We conclude albatrosses were able to exploit predictive cues from recent boat encounters but most favoured alternative resources.