Killer whales Orcinus orca have a cosmopolitan distribution with a broad diet ranging from fish to marine mammals. In Norway, killer whales are regularly observed feeding on overwintering Norwegian spring-spawning (NSS) herring Clupea harengus inside the fjords. However, their offshore foraging behavior and distribution are less well understood. In particular, it is not known to what degree they rely on the NSS herring stock when the herring move to deeper offshore waters. Satellite telemetry data from 29 male killer whales were analyzed to assess whether their offshore foraging behavior is linked to herring distribution. Unlike most marine predator-prey studies that use indirect proxies for prey abundance and distribution, our study utilized 2 herring density estimates based on (1) direct observations from acoustic trawl survey data and (2) simulations from a fully coupled ecosystem model. Mixed effects models were used to infer the effect of herring density and light intensity on whale movement patterns. Our results suggest that killer whales follow NSS herring over long distances along the coast from their inshore overwintering areas to offshore spawning grounds. All whales changed from fast, directed, to slow, non-directed movement when herring density increased, although individuals had different propensities towards movement. Our data indicated that whales continue to feed on herring along the Norwegian shelf. We conclude that NSS herring constitute an important prey resource for at least some killer whales in the northeastern Atlantic, not only during the herring overwintering period, but also subsequently throughout the herring spawning migration.