Quantifying animal movement in response to a spatially and temporally heterogeneous environment is critical to understanding the structural and functional landscape influences on population viability. Generalities of landscape structure can easily be extended to the marine environment, as marine predators inhabit a patchy, dynamic system, which influences animal choice and behavior. An innovative use of the fractal measure of complexity, indexing the linearity of movement paths over replicate temporal scales, was applied to satellite tracking data collected from narwhals (Monodon monoceros) (n = 20) in West Greenland and the eastern Canadian high Arctic. Daily movements of individuals were obtained using polar orbiting satellites via the ARGOS data location and collection system. Geographic positions were filtered to obtain a daily good quality position for each whale. The length of total pathway was measured over seven different temporal length scales (step lengths), ranging from one day to one week, and a seasonal mean was calculated. Fractal dimension (D) was significantly different between seasons, highest during summer (D = 1.61, SE 0.04) and winter (D = 1.69, SE 0.06) when whales made convoluted movements in focal areas. Fractal dimension was lowest during fall (D = 1.34, SE 0.03) when whales were migrating south ahead of the forming sea ice. There were no significant effects of size category or sex on fractal dimension by season. The greater linearity of movement during the migration period suggests individuals do not intensively forage on patchy resources until they arrive at summer or winter sites. The highly convoluted movements observed during summer and winter suggest foraging or searching efforts in localized areas. Significant differences between the fractal dimensions on two separate wintering grounds in Baffin Bay suggest differential movement patterns in response to the dynamics of sea ice.