The last two decades have witnessed great advances in reconstructing the transition from non-avian theropods to avians, but views in opposition to the theropod hypothesis still exist. Here we highlight one issue that is often considered to raise problems for the theropod hypothesis of avian origins, i.e. the “temporal paradox” in the stratigraphic distribution of theropod fossils - the idea that the earliest known avian is from the Late Jurassic but most other coelurosaurian groups are poorly known in the Jurassic, implying that avians arose before their supposed ancestors. However, a number of Jurassic non-avian coelurosaurian theropods have recently been discovered, thus documenting the presence of most of the major coelurosaurian groups in the Jurassic alongside, or prior to, avians. These discoveries have greatly improved the congruence between stratigraphy and phylogeny for derived theropods and, effectively, they reject the “temporal paradox” concept. Most importantly, these discoveries provide significant new information that supports the relatively basal positions of the Tyrannosauroidea and Alvarezsauroidea among the Coelurosauria. Indeed, they imply a new phylogenetic hypothesis for the interrelationships of Paraves, in which Archaeopteryx, the Dromaeosauridae, and the Troodontidae form a monophyletic group while the Scansoriopterygidae, other basal birds, and probably also the Oviraptorosauria, form another clade. Mapping some of the salient features onto a temporally-calibrated theropod phylogeny indicates that characteristics related to flight and arboreality evolved at the base of the Paraves, earlier than the Late Jurassic.