Seabird foraging activities are constrained by the heterogeneous distribution of prey, intra-specific competition, and the varying energy requirements throughout their life history. Investigations of intra-seasonal variation in foraging habitat will, therefore, provide clues to understand how predators respond to changes in the marine environment. As an abundant, central-place foraging mesopredator, we selected to examine this with Adélie penguins (Pygoscelis adeliae) breeding in the Prydz Bay region where the sea-ice environment is heterogeneous and the largest populations in East Antarctica occur. In the summer of 2011/12, using GPS tracks, we calculated First Passage Time to extract Area Restricted Search (ARS) zones to indicate foraging intensity, and classified the ARS zones by K-means clustering. In total, 47, 64, 23 and 10 ARS zones were detected during early and late incubation, chick-guard and crèche stages (n = 4, 11, 6 and 3 birds). Higher and more stable sea-ice concentration and increased distance from the nearest major colony had positive effects on foraging intensity. The ARS zones were classified into nearshore, offshore and open water habitats. Birds used offshore areas and avoided open water during early incubation and crèche, when birds returned less frequently. During late incubation and chick-guard, when birds frequently returned, they used nearshore and open water areas as expected from the proportion of available habitats. Our results suggest that the pack ice and reduced intra-specific competition for prey were the preferred foraging condition for Adélie penguins, and highlight the importance of seasonal changes in sea-ice environment to their foraging habitat selectivity.