Investigating ecological relationships between predators and their environment is essential to understand the response of marine ecosystems to climate variability and change. This is particularly true in polar regions, where sea ice (a sensitive climate variable) plays a crucial yet highly dynamic and variable role in how it influences the whole marine ecosystem, from phytoplankton to top predators. For mesopredators such as seals, sea ice both supports a rich (under-ice) food resource, access to which depends on local to regional coverage and conditions. Here, we investigate sex-specific relationships between the foraging strategies of southern elephant seals (Mirounga leonina) in winter and spatio-temporal variability in sea ice concentration (SIC) and coverage in East Antarctica. We satellite-tracked 46 individuals undertaking post-moult trips in winter from Kerguelen Islands to the peri-Antarctic shelf between 2004 and 2014. These data indicate distinct general patterns of sea ice usage: while females tended to follow the sea ice edge as it extended northward, the males remained on the continental shelf despite increasing sea ice. Seal hunting time, a proxy of foraging activity inferred from the diving behaviour, was longer for females in late autumn in the outer part of the pack ice, ∼150–370 km south of the ice edge. Within persistent regions of compact sea ice, females had a longer foraging activity (i) in the highest sea ice concentration at their position, but (ii) their foraging activity was longer when there were more patches of low concentration sea ice around their position (either in time or in space; 30 days & 50 km). The high spatio-temporal variability of sea ice around female positions is probably a key factor allowing them to exploit these concentrated patches. Despite lack of information on prey availability, females may exploit mesopelagic finfishes and squids that concentrate near the ice-water interface or within the water column (from diurnal vertical migration) in the pack ice region, likely attracted by an ice algal autumn bloom that sustains an under-ice ecosystem. In contrast, male foraging effort increased when they remained deep within the sea ice (420–960 km from the ice edge) over the shelf. Males had a longer foraging activity (i) in the lowest sea ice concentration at their position, and (ii) when there were more patches of low concentration sea ice around their position (either in time or in space; 30 days & 50 km) presumably in polynyas or flaw leads between land fast and pack ice. This provides access to zones of enhanced resources in autumn or in early spring such as polynyas, the Antarctic shelf and slope. Our results suggest that some seals utilized a highly sea ice covered environment, which is key for their foraging effort, sustaining or concentrating resources during winter.