Deer are an iconic group of large mammals that originated in the Early Miocene of Eurasia (ca. 19 Ma). While there is some consensus on key relationships among their members, on the basis of molecular- or morphology-based analyses, or combined approaches, many questions remain, and the bony labyrinth has shown considerable potential for the phylogenetics of this and other groups. Here we examine its shape in 29 species of living and fossil deer using 3D geometric morphometrics and cladistics. We clarify several issues of the origin and evolution of cervids. Our results give new age estimates at different nodes of the tree and provide for the first time a clear distinction of stem and crown Cervidae. We unambiguously attribute the fossil Euprox furcatus (13.8 Ma) to crown Cervidae, pushing back the origin of crown deer to (at least) 4 Ma. Furthermore, we show that Capreolinae are more variable in bony labyrinth shape than Cervinae and confirm for the first time the monophyly of the Old World Capreolinae (including the Chinese water deer Hydropotes) based on morphological characters only. Finally, we provide evidence to support the sister group relationship of Megaloceros giganteus with the fallow deer Dama.