A number of cupressaceous fossil leaves are described in this paper that come from the lower Miocene of Inner Mongolia, northern China. These new examples of fossil leaves are compressed, have their branchlets arranged in a plane, either spreading or ascending, and are flat. These specimens also possess scale-like leaves that are dimorphic, preserved facial leaves that are rhomboidal and have obtuse apices, and lateral leaves that are boat-shaped and have slightly incurved apices. The epidermal cells of these fossils are quadrangular, rectangular, or narrowly rectangular, while the leaves are amphistomatic, and stomata are elliptical or oblong, and monocyclic. In comparison with both living and related fossil taxa, we identify the new fossils as Platycladus preorientalis sp. nov. Taken in combination with a molecular phylogenetic analysis, the new fossils suggest that the genus Platycladus originated in the Oligocene in mid and high Asian latitudes. Thus, the ancient Platycladus lineage probably migrated from Europe to Asia following the closure of the Turgai strait during the Oligocene.