The holotype is MN 7019-V (earlier CB-PV-F-O93), from the Romualdo Member of the Santana Formation. This fossil, a single skull with a length of 57 centimetres, was discovered on the Araripe plateau in northeastern Brazil. It was traded to Italy in 1983 and bought by Borgomanero for his collection. The skull is severely damaged, especially on the top, and was perhaps reconstructed by the fossil dealer.
As shown by a later preparation by the Brazilian Museu Nacional, in the first preparation many serious mistakes were made. The fronts of the snout and of the lower jaws were confused leading to a reconstruction in which the anterior part of the head was upside down. The teeth were extensively restored and enlarged until the wider front of the jaws showed very large and robust teeth projecting outwards, forming a sort of "rosette". This kinked upper jaw and its interlocking teeth suggested a piscivourous diet, allowing the animal to keep hold of slippery fish. No crests seemed to be present. The new preparation made clear that a crest was present on the snout and that the rosette was a lot smaller. Many details were discovered that were useful in determining the phylogenetic position of Cearadactylus.
The wingspan of Cearadactylus was by the describers estimated to have been around 4 metres (13 ft), with a weight of perhaps 15 kilograms (33 lb). Peter Wellnhofer in 1991 estimated a wingspan of 5.5 metres (18 ft).
Leonardi did abstain from assigning the genus to a family. Wellnhofer created a special family Cearadactylidae, but this concept is no longer used. In 2000 Alexander Kellner concluded that it was related to, but lacking a crest not part of, the Anhangueridae within a larger Pteranodontoidea sensu Kellner. In 2002 David Unwin however stated it was a highly deviant member of Ctenochasmatidae. In 2010 Kellner entered the new information into three existing databases of pterosaur features, to calculate through cladistic analysis the position of Cearadactylus in the phylogenetic tree. Although the three resulting trees differed, all had in common that Cearadactylus was close to the Anhangueridae.