Bird-line archosaurs (= Avemetatarsalia, the clade containing birds, dinosaurs, pterosaurs, and their kin) originated in the Triassic Period. However, the earliest evolution of this group is poorly documented because fossils are extremely rare and consist mostly of postcrania. Here, we document the osteology of Teleocrater rhadinus, an early avemetatarsalian from the lower portion of the Middle Triassic Lifua Member of the Manda Beds of the Ruhuhu Basin, southwestern Tanzania. Material of Teleocrater rhadinus includes the holotype partial skeleton comprising a single individual, including cervical, trunk, and caudal vertebrae, pectoral, pelvic, forelimb, and hind limb material, and referred specimens representing parts (skull elements, vertebrae, pectoral, pelvic, and limb elements) of at least three other individuals collected from a bonebed. Character states of the skull elements, vertebrae, girdles, and limbs indicate that Teleocrater rhadinus represents the first documented non-ornithodiran avemetatarsalian known from well-preserved, associated material. Furthermore, Teleocrater rhadinus forms part of a newly recognized clade, Aphanosauria, which also contains formerly enigmatic archosaur taxa from across Pangea, including Dongusuchus efremovi from the Middle Triassic of Russia, Yarasuchus deccanensis from the Middle Triassic of India, and Spondylosoma absconditum from the ?Middle Triassic of Brazil. This new clade and other new discoveries from the Middle to Late Triassic elucidate the sequence of character acquisitions at the base of Avemetatarsalia and fill a crucial gap in the understanding of the anatomical transformations that enabled dinosaurs to flourish later in the Mesozoic.