The fossil record of tyrannosauroid theropods is marked by a substantial temporal and morphological gap between small-bodied, Barremian taxa, and extremely large-bodied taxa from the latest Cretaceous. Here we describe a new tyrannosauroid, Xiongguanlong baimoensis n. gen. et sp., from the Aptian-Albian Xinminpu Group of western China that represents a phylogenetic, morphological, and temporal link between these disjunct portions of tyrannosauroid evolutionary history. Xiongguanlong is recovered in our phylogenetic analysis as the sister taxon to Tyrannosauridae plus Appalachiosaurus, and marks the appearance of several tyrannosaurid hallmark features, including a sharp parietal sagittal crest, a boxy basicranium, a quadratojugal with a flaring dorsal process and a flexed caudal edge, premaxillary teeth bearing a median lingual ridge, and an expanded axial neural spine surmounted by distinct processes at its corners. Xiongguanlong is characterized by a narrow and elongate muzzle resembling that of Alioramus. The slender, unornamented nasals of Xiongguanlong are inconsistent with recent hypotheses of correlated progression in tyrannosauroid feeding mechanics, and suggest more complex patterns of character evolution in the integration of feeding adaptations in tyrannosaurids. Body mass estimates for the full-grown holotype specimen of Xiongguanlong fall between those of Late Cretaceous tyrannosaurids and Barremian tyrannosauroids, suggesting that the trend of increasing body size observed in North American Late Cretaceous Tyrannosauridae may extend through the Cretaceous history of Tyrannosauroidea though further phylogenetic work is required to corroborate this.