Predators specialising on migratory prey that frequently change migration route face the challenge of finding prey with an unpredictable distribution. Here, we used photo-identification data to investigate whether killer whales observed in herring overwintering and spawning grounds off Iceland follow herring year-round, as previously proposed, and have the ability to adapt to long-term changes in herring distribution. Of 327 identified whales seen more than once, 45% were seen in both grounds, and were thus presumed herring-specialists, likely following herring year-round, while others were only seen on one of the grounds, possibly following herring to unsampled grounds or moving to other locations and exploiting different prey. High seasonal site fidelity to herring grounds, long-term site fidelity to herring spawning grounds, and matches of individual whales between past and recently occupied herring overwintering grounds showed an ability to adapt to long-term changes in prey distribution as well as diversity of movement patterns which are maintained over time, likely as socially-learnt traditions. Such population structuring shows that the movement patterns and foraging ecology of herring-eating killer whales are more complex than previously assumed and must be taken into account in future population assessments. Identifying the factors driving these differences in movements and resource use will be relevant towards our understanding of how prey predictability may drive specialization in this and other top predator species.