The evolution of baleen whales (Mysticeti), the largest animals on Earth, was punctuated by a pivotal turnover event. Following their emergence around 36 million years (Ma), mysticetes diversified into a disparate range of toothed and toothless species until 23 Ma, but then nearly vanished from the global fossil record for the next five million years. Following this early Miocene “dark age”, toothless mysticetes spectacularly reappeared around 18–17 Ma, whereas toothed mysticetes had gone entirely extinct. Here, we suggest that this turnover event reflects a change in mysticete habitat occupancy. Using the well-sampled record of Australasia as a case study, we show that Oligocene pre-“dark age” mysticetes formed distinct coastal and offshore assemblages, dominated by small (2–4 m), ecologically disparate toothed species, and larger (5–6 m) toothless filter feeders, respectively. Environmental change around the Oligocene–Miocene boundary led to the decline of the endemic coastal assemblages, leaving nearshore deposits virtually devoid of mysticetes. Filter feeders persisted offshore and subsequently re-invaded coastal habitats during the mid-Miocene Climatic Optimum, thus establishing the modern, cosmopolitan mysticete fauna.