Assessing the migratory behaviour of individual and groups of animals is key to understand the function of migration, its evolution, and how it is affected by environment and human activities. In the eastern North Atlantic, killer whales (Orcinus orca) presumably track herring stocks as they migrate between across the region. However, the detailed migratory and foraging behaviour of eastern North Atlantic killer whales is poorly understood. We report on the behaviour of 15 adult male killer whales equipped with Argos satellite transmitters during the winter of 2015-2016 along the coast of Troms, northern Norway. The animals were tracked for 8-104 days (mean: 41 days), during which they migrated 302-7608 Km (mean: 2646 Km). The observed movement of killer whales south to 64.2 degrees N along the Norwegian coast following NSS-herring to their spawning grounds is in agreement with previous studies. However, our study is the first to also document northern migration of three of the Norwegian killer whales into the Barents Sea region towards Novaya Zemlya Island about 900 km from the Norwegian coast approaching 77.0 degrees N. Importantly, using a Bayesian state-space model, we offer new insights on killer whale searching and transit movements, as well as diurnal patterns in swimming speed, preferred foraging habitat and feeding behaviour. The 15 tagged killer whales spend 75.0% of the time in an area restricted search (ARS) mode (range: 55.2-95.2%), 3.9% of the time in a transit mode (range: 0.0-16.1%) and 21.1% (range: 4.8-36.3%) in uncertain mode. The restricted search behaviour peaked at the end of January and beginning of February, after which the killer whales gradually performing transit behaviour as they followed the migrating herring out of the region, or shifted to other prey items.