Two new genera and four new species of Palaeontinidae (Cicadomorpha), Baeocossus finchae gen. et sp. nov., Colossocossus loveridgei gen. et sp. nov., C. rugosa gen. et sp. nov. and Parawonnacottella penneyi sp. nov. are described from the Nova Olinda Member of the Upper Aptian (Lower Cretaceous) Crato Formation of Ceará, northeast Brazil. The diagnosis of the genus Parawonacottella Ueda is revised. The new taxa form a natural group with other Early Cretaceous forms including Cratocossus magnus Martins-Neto, also from the Crato Formation, and the “Ilerdocossus-complex” from the Berriasian–Valanginian of Montsec, Spain (Ilerdocossus Gomez-Pallerola = Wonnacottella Whalley and Jarzembowski) and the ?Hauterivian–Barremian of Liaoning and Hebei, China (Ilerdocossus = Liaocossus Ren, Yin and Duo, syn. nov.). Preliminary analysis of geographical distribution and relationships suggests that this group originated in Central or East Asia in the Middle Jurassic before spreading into Western Europe and South America. The distribution of the “Ilerdocossus-complex” supports a Late Jurassic exodus from Asia.