The Mesozoic Teleostei †Ichthyodectiformes presents a widespread distribution in marine brackish and freshwater deposits worldwide. The Brazilian fossil record of this group is represented by five nominal genera distributed exclusively in the sedimentary basins of Northeast Brazil (cf. Parnaíba, Sergipe-Alagoas, Recôncavo, Tucano, and Araripe). In the Araripe basin, the unique representative of the order is †Cladocyclus gardneri, restricted to the Crato and Romualdo Formations. Recent collecting efforts carried out in the Araripe Basin led to the discovery of two specimens of †Cladocyclidae. Based on the comparison with the known Brazilian taxa, we conclude that this new record represents a new genus and species of this clade. †Cladocynodon araripensis represents the first vertebrate described from the dark shales of the “Batateira Beds” of the Barbalha Formation and differs from the other †Cladocyclidae by the presence of hypertrophied bony fangs at the anterior region of the dentary, with other relatively small true teeth abruptly reduced posteriorly, and by presenting premaxillary and maxillary teeth significantly reduced in size. †Cladocynodon araripensis increases the anatomic diversity and temporal range of †Cladocyclidae in Gondwana.