The last two decades have seen a remarkable increase in the known diversity of basal avialans and their paravian relatives. The lack of resolution in the relationships of these groups combined with attributing the behavior of specialized taxa to the base of Paraves has clouded interpretations of the origin of avialan flight. Here, we describe Hesperornithoides miessleri gen. et sp. nov., a new paravian theropod from the Morrison Formation (Late Jurassic) of Wyoming, USA, represented by a single adult or subadult specimen comprising a partial, well-preserved skull and postcranial skeleton. Limb proportions firmly establish Hesperornithoides as occupying a terrestrial, non-volant lifestyle. Our phylogenetic analysis emphasizes extensive taxonomic sampling and robust character construction, recovering the new taxon most parsimoniously as a troodontid close to Daliansaurus, Xixiasaurus, and Sinusonasus. Multiple alternative paravian topologies have similar degrees of support, but proposals of basal paravian archaeopterygids, avialan microraptorians, and Rahonavis being closer to Pygostylia than archaeopterygids or unenlagiines are strongly rejected. All parsimonious results support the hypothesis that each early paravian clade was plesiomorphically flightless, raising the possibility that avian flight originated as late as the Late Jurassic or Early Cretaceous.