Afro-Arabian mammalian communities underwent a marked transition near the Oligocene/Miocene boundary at approximately 24 million years (Myr) ago. Although it is well documented that the endemic paenungulate taxa were replaced by migrants from the Northern Hemisphere, the timing and evolutionary dynamics of this transition have long been a mystery because faunas from about 32 to 24 Myr ago are largely unknown. Here we report a late Oligocene fossil assemblage from Ethiopia, which constrains the migration to postdate 27 Myr ago, and yields new insight into the indigenous faunal dynamics that preceded this event. The fauna is composed of large paenungulate herbivores and reveals not only which earlier taxa persisted into the late Oligocene epoch but also demonstrates that one group, the Proboscidea, underwent a marked diversification. When Eurasian immigrants entered Afro-Arabia, a pattern of winners and losers among the endemics emerged: less diverse taxa such as arsinoitheres became extinct, moderately species-rich groups such as hyracoids continued into the Miocene with reduced diversity, whereas the proboscideans successfully carried their adaptive radiation out of Afro-Arabia and across the world.