The Austral autumn–winter is a critical period for capital breeders such as Weddell seals that must optimize resource acquisition and storage to provision breeding in the subsequent spring. However, how Weddell seals find food in the winter months remains poorly documented. We equipped adult Weddell seals after their annual molt with satellite-relayed data loggers at two sites in East Antarctica: Dumont D'Urville (n = 12, DDU) and Davis (n = 20). We used binomial generalized mixed-effect models to investigate Weddell seals’ behavioral response (i.e., “hunting” vs. “transit”) to physical aspects of their environment (e.g., ice concentration). Weddell seal foraging was concentrated to within 5 km of a breathing hole, and they appear to move between holes as local food is depleted. There were regional differences in behavior so that seals at Davis traveled greater distances (three times more) and spent less time in hunting mode (half the time) than seals at DDU. Despite these differences, hunting dives at both locations were pelagic, concentrated in areas of high ice concentration, and over areas of complex bathymetry. There was also a seasonal change in diving behavior from transiting early in the season to more hunting during winter. Our observations suggest that Weddell seal foraging behavior is plastic and that they respond behaviorally to changes in their environment to maximize food acquisition and storage. Such plasticity is a hallmark of animals that live in very dynamic environments such as the high Antarctic where resources are unpredictable.