Background Sooty (Puffinus griseus) and short-tailed (P. tenuirostris) shearwaters are abundant seabirds that range widely across global oceans. Understanding the foraging ecology of these species in the Southern Ocean is important for monitoring and ecosystem conservation and management. Methodology/Principal Findings Tracking data from sooty and short-tailed shearwaters from three regions of New Zealand and Australia were combined with at-sea observations of shearwaters in the Southern Ocean, physical oceanography, near-surface copepod distributions, pelagic trawl data, and synoptic near-surface winds. Shearwaters from all three regions foraged in the Polar Front zone, and showed particular overlap in the region around 140°E. Short-tailed shearwaters from South Australia also foraged in Antarctic waters south of the Polar Front. The spatial distribution of shearwater foraging effort in the Polar Front zone was matched by patterns in large-scale upwelling, primary production, and abundances of copepods and myctophid fish. Oceanic winds were found to be broad determinants of foraging distribution, and of the flight paths taken by the birds on long foraging trips to Antarctic waters. Conclusions/Significance The shearwaters displayed foraging site fidelity and overlap of foraging habitat between species and populations that may enhance their utility as indicators of Southern Ocean ecosystems. The results highlight the importance of upwellings due to interactions of the Antarctic Circumpolar Current with large-scale bottom topography, and the corresponding localised increases in the productivity of the Polar Front ecosystem.