Phylogenetic relationships near the origin of extant crocodylians are weakly supported, and this lack of resolution makes for poor estimates of taxonomic and morphological diversity. Previously known taxa are found throughout the Cretaceous in Laurasia and at a few sites from Brazil, Australia, and northern Africa. Here, we report Batrachomimus pastosbonensis gen. et sp. nov. from the Late Jurassic of northeastern Brazil, which is deeply nested within Neosuchia and associated to the Cretaceous Asian paralligatorids. The new taxon predates all other members of Paralligatoridae and its immediate sister group (including Eusuchia) by 30 million years. A nearly complete skull, osteoderms, and limb bones were recovered, and autapomorphies of B. pastosbonensis include a scalloped lateral margin of the rostrum in dorsal view, unsculpted alveolar margin at the caudalmost portion of the maxilla, blunt lateral prongs on the jugal at the base of the postorbital bar, hourglass shaped choanae, and pterygoid choanal septum extended between the palatal shelves of the palatines. The crocodyloid-like skull proportions and the slender, conical teeth suggest an amphibious and piscivorous life history to this 1 m long animal.