Birds, dinosaurs, crocodilians, pterosaurs and their close relatives form the highly diverse clade Archosauriformes. Archosauriforms have a deep evolutionary history, originating in the late Permian, prior to the end-Permian mass extinction, and radiating in the Triassic to dominate Mesozoic ecosystems. However, the origins of this clade and its extraordinarily successful body plan remain obscure. Here, we describe an exceptionally preserved fossil skull from the Lower Triassic of Brazil, representing a new species, Teyujagua paradoxa, transitional in morphology between archosauriforms and more primitive reptiles. This skull reveals for the first time the mosaic assembly of key features of the archosauriform skull, including the antorbital and mandibular fenestrae, serrated teeth, and closed lower temporal bar. Phylogenetic analysis recovers Teyujagua as the sister taxon to Archosauriformes, and is congruent with a two-phase model of early archosauriform evolution, in response to two mass extinctions occurring at the end of the Guadalupian and the Permian.