Early members of the dinosaur-pterosaur clade Ornithodira are very rare in the fossil record, obscuring our understanding of the origins of this important group. Here, we describe an early ornithodiran (Kongonaphon kely gen. et sp. nov.) from the Mid-to-Upper Triassic of Madagascar that represents one of the smallest nonavian ornithodirans. Although dinosaurs and gigantism are practically synonymous, an analysis of body size evolution in dinosaurs and other archosaurs in the context of this taxon and related forms demonstrates that the earliest-diverging members of the group may have been smaller than previously thought, and that a profound miniaturization event occurred near the base of the avian stem lineage. In phylogenetic analysis, Kongonaphon is recovered as a member of the Triassic ornithodiran clade Lagerpetidae, expanding the range of this group into Africa and providing data on the craniodental morphology of lagerpetids. The conical teeth of Kongonaphon exhibit pitted microwear consistent with a diet of hard-shelled insects, indicating a shift in trophic ecology to insectivory associated with diminutive body size. Small ancestral body size suggests that the extreme rarity of early ornithodirans in the fossil record owes more to taphonomic artifact than true reflection of the group's evolutionary history.