Southern Ocean ecosystems are rapidly changing due to climate variability. An apparent beneficiary of such change in the western Antarctic Peninsula (WAP) is the gentoo penguinPygoscelis papua, which has increased its population size and expanded its range southward in the last 20 years. To better understand how this species has responded to large-scale changes, we tracked individuals during the non-breeding winter period from five colonies across the latitudinal range of breeding sites in the WAP, including from a recently established colony. Results highlight latitudinal gradients in movement; strong associations with shallow, coastal habitats along the entire Antarctic Peninsula; and movements that are independent of, yet constrained by, sea ice. It is clear that coastal habitats essential to gentoo penguins during the breeding season are similarly critical during winter. Larger movements of birds from northern colonies in the WAP further suggest that leap-frog migration may influence colonization events by facilitating nest-area prospecting and use of new haul-out sites. Our results support efforts to develop a marine protected area around the WAP. Winter habitats used by gentoo penguins outline high priority areas for improving the management of the spatio-temporally concentrated krill (Euphausia superba) fishery that operates in this region during winter.