An edentulous partial skeleton of a carnivorous mammal from the Uinta Formation (middle Eocene) of Utah is referred to the rare and enigmatic sabre-tooth clade Machaeroidinae primarily on the basis of alveolar patterns and cranial morphology. The newly recognized skeleton includes portions of both girdles, all long bones, and the first known tarsal and phalangeal material of a machaeroidine. The specimen permits a preliminary reconstruction of the locomotor habits of machaeroidines, which appear to have been adapted to scansorial or arboreal rather than terrestrial locomotion. The new material also prompts a review of machaeroidine affinities, which have been unresolved for over a century, with consensus opinion favouring a link to either oxyaenid or limnocyonine hyaenodontid ‘creodonts’. Postcranial evidence favours a link to oxyaenids, as machaeroidines share numerous features with oxyaenids that are lacking in hyaenodontids. To test this relationship machaeroidines were included in a phylogenetic analysis broadly sampling early carnivorous eutherians, including members of both ‘Creodonta’ and Carnivoramorpha. Results place Machaeroidinae within Oxyaenidae but fail to support either ‘creodont’ or carnivoramorphan monophyly. Instead, Oxyaenidae is linked with Carnivoraformes, while Viverravidae is basally positioned among carnivorous eutherians. Reconsideration of the character evidence cited in support of Carnivoramorpha indicates that many features are ambiguous in the context of a broad sample of ‘creodonts’ and early carnivoramorphans. Hyaenodontid monophyly is also not recovered but this likely reflects the influence of one morphologically divergent genus, Arfia.