Dust has the potential to modify global climate by influencing the radiative balance of the atmosphere and by supplying iron and other essential limiting micronutrients to the ocean. Indeed, dust supply to the Southern Ocean increases during ice ages, and 'iron fertilization' of the subantarctic zone may have contributed up to 40 parts per million by volume (p.p.m.v.) of the decrease (80-100 p.p.m.v.) in atmospheric carbon dioxide observed during late Pleistocene glacial cycles. So far, however, the magnitude of Southern Ocean dust deposition in earlier times and its role in the development and evolution of Pleistocene glacial cycles have remained unclear. Here we report a high-resolution record of dust and iron supply to the Southern Ocean over the past four million years, derived from the analysis of marine sediments from ODP Site 1090, located in the Atlantic sector of the subantarctic zone. The close correspondence of our dust and iron deposition records with Antarctic ice core reconstructions of dust flux covering the past 800,000 years (refs 8, 9) indicates that both of these archives record large-scale deposition changes that should apply to most of the Southern Ocean, validating previous interpretations of the ice core data. The extension of the record beyond the interval covered by the Antarctic ice cores reveals that, in contrast to the relatively gradual intensification of glacial cycles over the past three million years, Southern Ocean dust and iron flux rose sharply at the Mid-Pleistocene climatic transition around 1.25 million years ago. This finding complements previous observations over late Pleistocene glacial cycles, providing new evidence of a tight connection between high dust input to the Southern Ocean and the emergence of the deep glaciations that characterize the past one million years of Earth history.