The Miocene was a key time in the evolution of African ecosystems witnessing the origin of the African apes and the isolation of eastern coastal forests through an expanding arid corridor. Until recently, however, Miocene sites from the southeastern regions of the continent were unknown. Here we report the first Miocene fossil teeth from the shoulders of the Urema Rift in Gorongosa National Park, Mozambique. We provide the first 1) radiometric ages of the Mazamba Formation, 2) reconstructions of paleovegetation in the region based on pedogenic carbonates and fossil wood, and 3) descriptions of fossil teeth. Gorongosa is unique in the East African Rift in combining marine invertebrates, marine vertebrates, reptiles, terrestrial mammals, and fossil woods in coastal paleoenvironments. The Gorongosa fossil sites offer the first evidence of woodlands and forests on the coastal margins of southeastern Africa during the Miocene, and an exceptional assemblage of fossils including new species.