Fossil crocodyliforms discovered in recent years have revealed a level of morphological and ecological diversity not exhibited by extant members of the group. This diversity is particularly notable among taxa of the Cretaceous Period (144-65 million years ago) recovered from former Gondwanan landmasses. Here we report the discovery of a new species of Cretaceous notosuchian crocodyliform from the Rukwa Rift Basin of southwestern Tanzania. This small-bodied form deviates significantly from more typical crocodyliform craniodental morphologies, having a short, broad skull, robust lower jaw, and a dentition with relatively few teeth that nonetheless show marked heterodonty. The presence of morphologically complex, complementary upper and lower molariform teeth suggests a degree of crown-crown contact during jaw adduction that is unmatched among known crocodyliforms, paralleling the level of occlusal complexity seen in mammals and their extinct relatives. The presence of another small-bodied mammal-like crocodyliform in the Cretaceous of Gondwana indicates that notosuchians probably filled niches and inhabited ecomorphospace that were otherwise occupied by mammals on northern continents.