Taxaceae (the yew family) are a relict family of conifers, with most species having a highly restricted or fragmentary distribution in the northern hemisphere and New Caledonia. Fossil data indicate that the family had diverged by the earliest Jurassic in southern Sweden, and extant taxaceous genera might had appeared since the Jurassic. In this article, we describe a new genus and species of extinct Taxaceae, Palaeotorreya shenghuii gen. et sp. nov., based on lignified leaves from the Lower Cretaceous Huolinhe Formation in West Ujimqin Banner, eastern Inner Mongolia, Northeast China. The leaves of Palaeotorreya shenghuii are linear to linear-lanceolate and hypostomatic. Epidermal cells of adaxial epidermis and non-stomatal zones of abaxial epidermis are strongly elongated. Two lateral stomatal bands on the abaxial leaf surface are narrow and sunken, each is flanked and concealed by two folding edges bearing dense and prominent papillae. Stomata are longitudinally oriented and arranged in short longitudinal files. Stomata are haplocheilic, stomatal complexes are monocyclic, with a complete and solid stomatal ring surrounding the stomatal pit on the outer cuticle surface. Palaeotorreya shenghuii is most comparable with Torreya within extant conifers, but also bears resemblance in stomatal structure to other genera of extant Taxaceae. The new fossils add to our knowledge of the diversity of the yew family during the Early Cretaceous.