The enigmatic tetrapod Acherontiscus caledoniae from the Pendleian stage of the Early Carboniferous shows heterodontous and durophagous teeth, representing the earliest known examples of significant adaptations in tetrapod dental morphology. Tetrapods of the Late Devonian and Early Carboniferous (Mississippian), now known in some depth, are generally conservative in their dentition and body morphologies. Their teeth are simple and uniform, being cone-like and sometimes recurved at the tip. Modifications such as keels occur for the first time in Early Carboniferous Tournaisian tetrapods. Acherontiscus, dated as from the Pendleian stage, is notable for being very small with a skull length of about 15 mm, having an elongate vertebral column and being limbless. Cladistic analysis places it close to the Early Carboniferous adelospondyls, aïstopods and colosteids and supports the hypothesis of 'lepospondyl' polyphyly. Heterodonty is associated with a varied diet in tetrapods, while durophagy suggests a diet that includes hard tissue such as chitin or shells. The mid-Carboniferous saw a significant increase in morphological innovation among tetrapods, with an expanded diversity of body forms, skull shapes and dentitions appearing for the first time.