Crocodylomorphs originated in the Late Triassic and were the only crocodile-line archosaurs to survive the end-Triassic extinction. Recent phylogenetic analyses suggest that the closest relatives of these generally gracile, small-bodied taxa were a group of robust, large-bodied predators known as rauisuchids implying a problematic morphological gap between early crocodylomorphs and their closest relatives. Here we provide a detailed osteological description of the recently named early diverging crocodylomorph Carnufex carolinensis from the Upper Triassic Pekin Formation of North Carolina and assess its phylogenetic position within the Paracrocodylomorpha. Carnufex displays a mosaic of crocodylomorph, rauisuchid, and dinosaurian characters, as well as highly laminar cranial elements and vertebrae, ornamented dermal skull bones, a large, subtriangular antorbital fenestra, and a reduced forelimb. A phylogenetic analysis utilizing a comprehensive dataset of early paracrocodylomorphs and including seven new characters and numerous modifications to characters culled from the literature recovers Carnufex carolinensis as one of the most basal members of Crocodylomorpha, in a polytomy with two other large bodied taxa (CM 73372 and Redondavenator). The analysis also resulted in increased resolution within Crocodylomorpha and a monophyletic clade containing the holotype and two referred specimens of Hesperosuchus as well as Dromicosuchus. Carnufex occupies a key transition at the origin of Crocodylomorpha, indicating that the morphology typifying early crocodylomorphs appeared before the shift to small body size.