The inner ear is a relatively small organ that provides key functions in vertebrates, such as hearing, balance, and spatial perception. Through fossilization, the soft tissues are not preserved, but the bony labyrinth, surrounding the inner ear, can be used as a proxy to investigate inner ear shape. Because of its fundamental role in coordinating movements, morphological differences of the inner ear between species and across groups could reflect locomotor specializations (whether terrestrial or arboreal, etc) and/or phylogenetic relationships. To test these hypotheses, and to investigate the evolution of this sensorial organ through time, we scanned the cranium of four extinct (~30-50 Ma) basal Carnivoramorpha species and one extinct (~50 Ma) species of Creodonta (a close relative), using high-resolution X-ray micro-CT (Computed Tomography). Succeeding, we reconstructed three-dimensional (3-D) inner ears from the bony labyrinth cavities. Our reconstructions are the first for these extinct species and of any fossil stem-carnivoramorphan. Landmarks were placed on the 3-D models and compared with a previously published dataset for extant species of Carnivoramorpha with known locomotor styles and phylogenetic relationships. Geometric morphometric analyses of both extant and extinct species reveal significant differences in inner ear shape (i.e. vestibular system) that correlate to different locomotor styles, as inferred by postcranial elements for the fossils, and phylogenetic proximity. Being able to distinguish locomotor capacities based on the inner ear shape of extant species could considerably improve insights into paleoecology and paleoenvironments. Ultimately, it also may provide crucial information on environmental changes that might have driven locomotor adaptations.