In western Europe, the Eocene-Oligocene boundary is associated with the influx of multiple clades of Asian mammals. However, Asian mammal clades appear in southeastern Europe 5-10 million years prior the Oligocene. How and when these clades colonized southeastern Europe remains poorly understood, partly because the Eocene fossil record of mammals from nearby Anatolia is characterized by marked endemism and limited exchanges with Asia. We resolve this apparent paradox by documenting the oldest Asian perissodactyls found so far in Anatolia, which date to the lower or middle Priabonian on the basis of geochronological, magnetostratigraphic, and biostratigraphic data. We show that the Eocene distribution of mammals across Eurasia supports a previously unrecognized biogeographic province, designated as Balkanatolia, spanning the Neotethyan margin from the Balkans to the Caucasus. The Eocene fossil record supports Balkanatolia having been colonized by Asian ungulates and rodents by the late Bartonian, following a drop in eustatic sea level and a tectonically-driven sea retreat in eastern Anatolia and the Lesser Caucasus. These paleogeographic changes instigated the demise of Balkanatolia as a distinct biogeographic province and paved the way for later dispersals in western Europe.