Individual foraging specializations, where individuals use a small component of the population niche width, are widespread in nature with important ecological and evolutionary implications. In long-lived animals, foraging ability develops with age, but we know little about the ontogeny of individuality in foraging. Here we use precision global positioning system (GPS) loggers to examine how individual foraging site fidelity (IFSF), a common component of foraging specialization, varies between breeders, failed breeders and immatures in a long-lived marine predator—the northern gannet Morus bassanus . Breeders (aged 5+) showed strong IFSF: they had similar routes and were faithful to distal points during successive trips. However, centrally placed immatures (aged 2–3) were far more exploratory and lacked route or foraging site fidelity. Failed breeders were intermediate: some with strong fidelity, others being more exploratory. Individual foraging specializations were previously thought to arise as a function of heritable phenotypic differences or via social transmission. Our results instead suggest a third alternative—in long-lived species foraging sites are learned during exploratory behaviours early in life, which become canalized with age and experience, and refined where possible—the exploration-refinement foraging hypothesis. We speculate similar patterns may be present in other long-lived species and moreover that long periods of immaturity may be a consequence of such memory-based individual foraging strategies.