The Miocene is a key time in the evolution of African mammals and their ecosystems witnessing the origin of the African apes and the isolation of eastern coastal forests through an expanding biogeographic arid corridor. Until recently, however, Miocene sites from the southeastern regions of the continent were unknown. Here we report discovery of the first Miocene fossil teeth from the shoulders of the Urema Rift in Gorongosa National Park, Mozambique, at the southern East African Rift System. We provide the first 1) radiometric age determinations of the fossiliferous Mazamba Formation, 2) reconstructions of past vegetation in the region based on pedogenic carbonates and fossil wood, and 3) description of fossil teeth from the southern rift. Gorongosa is unique in the East African Rift System in combining marine invertebrates, marine vertebrates, terrestrial mammals, and fossil woods in coastal paleoenvironments. The Gorongosa fossil sites offer the first evidence of persistent woodlands and forests on the coastal margins of southeastern Africa during the Miocene, and an exceptional assemblage of fossil vertebrates including new species. Further work will allow the testing of hypotheses positing the formation of a northeast-southwest arid corridor isolating species on the eastern coastal forests from those elsewhere in Africa.