The circum-Antarctic Southern Ocean is an important region for global marine food webs and carbon cycling because of sea-ice formation and its unique plankton ecosystem. However, the mechanisms underlying the installation of this distinct ecosystem and the geological timing of its development remain unknown. Here, we show, on the basis of fossil marine dinoflagellate cyst records, that a major restructuring of the Southern Ocean plankton ecosystem occurred abruptly and concomitant with the first major Antarctic glaciation in the earliest Oligocene (~33.6 million years ago). This turnover marks a regime shift in zooplankton-phytoplankton interactions and community structure, which indicates the appearance of eutrophic and seasonally productive environments on the Antarctic margin. We conclude that earliest Oligocene cooling, ice-sheet expansion, and subsequent sea-ice formation were important drivers of biotic evolution in the Southern Ocean.