Context <p>Theoretical research has considered how animals should optimise foraging strategies to maximise fitness, adapting search scale to exploit different habitats and minimise competition. Empirical studies have described multi-scale area-restricted search (ARS) strategies for some species, but the physical and biological mechanisms underpinning such behaviour are rarely studied.</p> Objectives <p>Our objectives were to quantify the presence, prevalence, and habitat associations of scale-dependent foraging for two sympatric seal species, accounting for regional variation across the seascape.</p> Methods <p>We analyse a GPS telemetry dataset of 116 grey (<i>Halichoerus grypus</i>) and 325 harbour seals (<i>Phoca vitulina</i>) tracked throughout the North Sea. We test the existence of multi-scale ARS, comparing hidden Markov models (HMMs) with two ARS states against more conventional HMMs (one ARS state). We quantify regional variation and examine the scale-dependence of foraging habitat associations using <i>post-hoc</i> “use-encounter” models.</p> Results <p>Both species exhibited nested broad-scale and focussed ARS. Accounting for scale resulted in increases of up to 25% and 46% in inferred ARS for grey and harbour seals respectively. The prevalence and habitat associations of different ARS scales varied in a regional species-specific manner.</p> Conclusions <p>We demonstrate the first application of HMMs to capture multi-scale ARS from animal-borne tracking data. Overlooking scale-dependence may mask individual variation and underestimate ARS, with consequences for ecological understanding and conservation applications. We hypothesise that seals employ different search scales for different habitats, competition levels and/or prey types. We call for further research to elucidate the prevalence and ecological significance of this phenomenon in other aquatic predators.</p>