Notosuchians comprise a clade of mostly terrestrial crocodyliforms generally found in Cretaceous Gondwanan deposits. They evolved into many forms and some species show convergences with mammalian features such as the development of a high degree of heterodonty and multicuspid teeth. South American deposits concentrate the highest number of described notosuchian species, which is more than twice the number of taxa known from strata elsewhere. Here, a novel candidodontid notosuchian, Thilastikosuchus scutorectangularis, gen. et sp. nov., is presented and described, comprising a new monospecific genus and the oldest notosuchian record found in Brazil, and likely from South America. This new taxon lacks the sharp hypertrophied caniniform teeth of closely related forms, such as Malawisuchus and Pakasuchus, but shares the posterior molariform teeth with increasingly wider crowns and denticulated cingula. Additionally, the phylogenetic analysis with the inclusion of the new Brazilian material places Candidodontidae as the earliest notosuchian radiation, shedding new light into its origins.