The East African Rift System (EARS) has played a central role in our understanding of human origins and vertebrate evolution in the late Cenozoic of Africa. However, the distribution of fossil sites along the rift is highly biased towards its northern extent, and the types of paleoenvironments are primarily restricted to fluvial and lacustrine settings. Here we report the discovery of the first fossil sites from the Urema Rift at Gorongosa National Park (central Mozambique) at the southern end of the EARS, and reconstruct environmental contexts of the fossils. In situ and surface fossils from the lower member of the Mazamba Formation, estimated to be of Miocene age, comprise mammals, reptiles, fishes, invertebrates, palms, and dicot trees. Fossil and geological evidence indicates a coastal-plain paleoenvironmental mosaic of riverine forest/woodland and estuarine habitats that represent the first coastal biomes identified in the Neogene EARS context. Receiving continental sediment from source terranes west of today's Urema Graben, estuarine sequences accumulated prior to rifting as compound incised-valley fills on a low-gradient coastal plain following transgression. Modern environmental analogues are extremely productive habitats for marine and terrestrial fauna, including primates. Thus, our discoveries raise the possibility that the Miocene coastal landscapes of Gorongosa were ecologically-favorable habitats for primates, providing relatively stable maritime climate and ecosystem conditions, year-round freshwater availability, and food both from terrestrial and marine sources. The emerging fossil record from Gorongosa is beginning to fill an important gap in the paleobiogeography of Africa as no fossil sites of Neogene age have previously been reported from the southernmost part of the EARS. Furthermore, this unique window into past continental-margin ecosystems of central Mozambique may allow us to test key paleobiogeographic hypotheses during critical periods of primate evolution.