The ?Early Cretaceous (pre-Aptian) Missão Velha Formation of the Araripe Basin of North-East Brazil yields remains referred to two hybodontiform shark taxa: the hybodontid Planohybodus and the lonchidiid Parvodus. Paleoenvironmental analysis of this formation suggests freshwater or perhaps brackish deposition. The specimens described here were collected from a new locality and are found in association with actinopterygian and sarcopterygian fishes and rarer turtles, crocodylomorphs and theropod dinosaurs. The chondrichthyan assemblage is represented by isolated teeth, cephalic spines, and dorsal fin spines. This is the first record of Planohybodus in the Araripe Basin and the first record of Parvodus in the Cretaceous of Gondwana.