Mixodectids are poorly understood placental mammals from the Paleocene of western North America that have variably been considered close relatives of euarchontan mammals (primates, dermopterans, and scandentians) with hypothesized relationships to colugos, extinct plagiomenids, and/or microsyopid plesiadapiforms. Here we describe the most complete dentally associated skeleton yet recovered for a mixodectid, specifically Mixodectes pungens from the early Paleocene of the San Juan Basin, New Mexico. A partial skull with all the teeth erupted and associated axial skeleton, forelimbs, and hind limbs, with epiphyses fused, indicate that it was a mature adult. Results from cladistic analyses incorporating new data robustly support primatomorphan (Primates + Dermoptera) affinities of Mixodectidae, but relationships within Euarchonta are less clear, with Mixodectes recovered as a stem primatomorphan, stem dermopteran, or stem primate. Analyses of postcrania suggest that M. pungens was a relatively large (~ 1.3 kg), claw-climbing arborealist capable of frequent clinging on large diameter vertical supports. With teeth suggesting an omnivorous diet that included leaves, M. pungens occupied a unique ecological niche in the early Paleocene of North America that differed from contemporary, arboreal plesiadapiforms that were smaller and more frugivorous. Euarchontans were thus a more diverse radiation in the early Cenozoic than previously appreciated.