The ear region of mammals has long been considered as morphologically very conservative and accordingly, phylogenetically useful. In this study, the anatomy of the petrosal and bony labyrinth (osseous inner ear) of Numidotherium (Proboscidea) and Arsinoitherium (Embrithopoda) are investigated and compared in order to assess the evolution of ear region characters in proboscideans and embrithopods. Using a cladistic analysis across Paenungulata based on ear region characters only, we found that Arsinoitherium is surprisingly best placed as a crown proboscideans to the exclusion of Numidotherium and Phosphatherium, which results in the paraphyly of proboscidean. The clade Proboscidea is actually well supported by dental and post-cranial characters, and we propose that this result underlines the great amount of morphological convergences in the ear region of Embrithopoda and Proboscidea, possibly due to convergent evolution of capabilities toward infrasonic hearing.