Finding scattered resources is a challenge for marine predators, their search strategies shaping in turn their response to global changes. Three types of search strategies are generally considered: random opportunistic search, reliance on conspicuous social cues or long-term individual fidelity to predictably productive areas. More complex strategies, namely intermediate, composite and/or those varying across time and environmental conditions are likely to prevail but are rarely explored. We investigated memory strategies in Cape gannets, a marine predator heavily relying on social cues, and closely related to the northern gannet which shows long-term individual foraging fidelity. Repeat GPS tracks within seasons revealed that two different individuals leaving the colony more than 3 days apart showed random chances to forage in a similar direction, whereas within-individuals, birds persisted in a same direction for longer timescales, reaching random levels only after 10 days, or 9 consecutive trips. This strategy of transient individual preferences within a breeding season was observed in most individuals every year. These results suggest a consistent and complex search strategy mixing social cues and private information updated every few days. Our simple approach can readily be applied to other central place foragers to better understand the evolutionary ecology of search strategies.