Troodontidae is an important dinosaur taxon that closely resembles birds in both morphology and biology. The evolution of troodontids is crucial for understanding evolutionary transitions between non-avialan theropods and avialans. Despite the recent discovery of several troodontid taxa across the world and many new studies of coelurosaurian relationships, an overall survey of morphological variation in troodontids and a comprehensive analysis of ingroup troodontid relationships have yet to be accomplished. In the first four chapters of this dissertation, the osteology of two new troodontid taxa and two closely related paravians are described in detail. These descriptions are based on new specimens recovered from the Mesozoic of China and Mongolia. These new taxa include the basal dromaeosaurid Microraptor zhaoianus, the basal avialan Anchiornis huxleyi, a new troodontid taxon represented by IGM 100/1323, and a second new troodontid taxon represented by IGM 100/1126 and IGM 100/3500. These paravian taxa are all small-sized, with a basal paravian body plan resembling Archaeopteryx, yet they represent members of all three major paravian lineages (Troodontidae, Dromaeosauridae and Avialae), and support the traditionally recognized paravian interrelationships. Osteological description of Microraptor zhaoianus is based on an excellently preserved new specimen BMNHC PH881. This specimen preserves significant morphological details that are not present, or are poorly preserved, in the other Microraptor specimens, including aspects of the skull, rib cage, and humerus. These new characters corroborate Microraptor as a member of the Dromaeosauridae and support the close relationship of troodontids with dromaeosaurids. Four new specimens (PKUVP 1068; BMNHC PH804, BMNHC PH822 and BMNHC PH823) of Anchiornis huxleyi reveal new osteological details of this important paravian taxon. Anchiornis huxleyi shares derived features with avialans, but it lacks derived deinonychosaurian characteristics such as a laterally exposed splenial and a specialized raptorial pedal digit II. IGM 100/1323 represents a new troodontid taxon from the Late Cretaceous Djadokhta Formation of Mongolia, diagnosed from other troodontids by the absence of the lateral groove on the dentary, a posteriorly curved pterygoid flange, a distinct spike-like process on the ischium, and elongate chevrons. Despite generally having a basal paravian body plan, IGM 100/1323 displays many derived troodontid features. IGM 100/1126 and IGM 100/3500 represent another new Late Cretaceous troodontid taxon from the Djadokhta-Formation-like rocks at Ukhaa Tolgod, Mongolia. It is unique and distinct from other troodontids in having closely packed peg-like teeth, a twisted suborbital process of the jugal, a quadratojugal with a crescentic ascending process that braces the quadrate posteriorly, reduction of the basal tubera, and presence of a posterior fossa on the proximal fibula. This new taxon is morphologically more derived than Early Cretaceous troodontids but is more primitive than other Late Cretaceous troodontids. A new and comprehensive phylogenetic analysis of coelurosaurian theropods, focusing on troodontids is presented in Chapter 5. This is an updated version of the Theropod Working Group (TWiG) analysis (2015.1). This new analysis incorporates new paravian taxa and new characters, most of which are relevant to paravians, especially the troodontids that are the focus of this dissertation. The new phylogenetic analysis agrees with previous studies on the general relationships of coelurosaurians, yet some important differences from previous TWiG analyses are present in paravians, including: 1), the Jianchang paravians are recovered as basal avialans; 2), Late Cretaceous troodontids form a monophyletic group; and 3), Jinfengopteryginae is not monophyletic.