The Red Sandstone Group (RSG) in the Rukwa Rift Basin of southwestern Tanzania represents one of the only well-exposed, fossiliferous Cretaceous–Paleogene continental sedimentary sequences in sub-equatorial Africa. The significance of the RSG for reconstructing the paleoenvironmental and paleoclimatic history of African ecosystems during these critical time periods has been obfuscated by long-standing confusion and debate over the age of the deposits. Detailed stratigraphic, sedimentologic, and paleontologic investigations of the RSG conducted between 2002 and 2008 have produced a wealth of new fossil discoveries and data on lithofacies, alluvial architecture, sedimentary provenance, clay mineralogy and geochronology that resolve the long-standing debate over the age of these deposits. This study confirms the existence of an extensive middle Cretaceous sequence, herein named the Galula Formation, and subdivided into the Mtuka and Namba members. Moreover, we document the existence of a previously unrecognized late Paleogene continental sequence termed the Nsungwe Formation, which is divided into the Utengule and Songwe members. The Galula Formation represents a 600-3000 m thick sequence of amalgamated, braided fluvial deposits that were deposited across a large braidplain system via multiple parallel channels that had their source in the highlands of Malawi and Zambia. The middle Cretaceous Dinosaur Beds of Malawi are hypothesized to be at least partially correlative with the Galula Formation, and represent proximal deposits of this large, northwest flowing, trunk stream system. A moderately diverse terrestrial vertebrate fauna, including multiple species of dinosaurs, crocodyliforms, turtles, fishes and mammals have been recovered, along with a sparse aquatic molluscan fauna. Lithofacies and clay mineralogy indicate that Cretaceous paleoclimate ameliorated during deposition of the Galula Formation, transitioning from tropical semi-arid to tropical humid conditions. The 400+ m-thick late Oligocene Nsungwe Formation is temporally constrained by concordant mammalian biostratigraphy, detrital zircon geochronology and a radiometrically dated volcanic tuff capping the sequence (not, vert, similar24.9 Ma). A significant change in depositional environments occurs between the lower alluvial fan-dominated Utengule Member and the upper fluvial and lacustrine-dominated Songwe Member. The Songwe Member preserves a diverse terrestrial and aquatic vertebrate and invertebrate fauna, with abundant ashfall and ashflow volcanic tuffs that were deposited in a semi-arid wetland landscape during the late Oligocene. The Nsungwe Formation provides a new window into the early tectonics and faunal transitions associated with initiation of the "modern" East African Rift System.