The diversification of the relict genus Calocedrus Kurz (Cupressaceae) in the Neogene of eastern Asia has remained unknown due to lack of fossil evidence. A late Miocene species, Calocedrus shengxianensis (He, Sun et Liu) Zhang et Zhou comb. nov., is described on the basis of new fossil material from the Wenshan flora in SE Yunnan, SW China. The species was originally described as Fokienia shengxianensis He, Sun et Liu from the upper Miocene Shengxian flora in E Zhejiang, SE China. The new fossil material includes well-preserved compression of leafy shoots and associated impression of seed cones. Based on the comparisons, this fossil species bears most similarities to the modern Calocedrus macrolepis Kurz, which is presently endemic to eastern Asia, in N India, Laos, NE Myanmar, NE Thailand, Vietnam and S China, but does not occur in SE Yunnan and E Zhejiang. The difference between them lies primarily in the morphology of apex of lateral as well as facial leaves. With the global cooling and uplift of the Qinghai–Tibet Plateau since the late Miocene, the climate in eastern Asia has changed profoundly. This has led to the disappearance of C. shengxianensis from SE Yunnan and E Zhejiang, and the leaf morphological shifts in C. macrolepis: the acute or acuminate leaf apices in the modern C. macrolepis, which are in contrast to the blunt or obtuse ones in the late Miocene C. shengxianensis, have evolved probably to adapt to the humid climate since the late Miocene.