As the largest intracontinental basin in the Tibetan Plateau hinterland, the Hoh Xil Basin is an ideal area for exploring the coupled history of climate-tectonic relationships in the plateau's interior. However, the detailed paleoenvironmental research on the Hoh Xil Basin is quite insufficient. In this study, we collected palynological and ostracod samples from well-exposed Cenozoic lacustrine strata in the Hoh Xil Basin to reconstruct the paleoenvironment and paleoelevation of the Hoh Xil Basin. Based on the discovery of two key index fossils (Austrocypris cf. posticaudata and Lychnothamnus vectensis), we propose the latest Eocene-early Oligocene (latest Priabonian-earliest Rupelian) age for the strata of the Yaxicuo Formation in the Tongtianhe section. The palynological assemblage suggests that the Hoh Xil Basin was dominated by temperate broadleaved forest and that a warm climate prevailed in this region during the latest Eocene-early Oligocene. Roughly consistent with the overall warm climate confirmed by palynological evidence, the ostracod record indicates that a large freshwater lake existed within the warm environment of the Hoh Xil Basin during the latest Eocene-early Oligocene. By using the coexistence approach (CoA) to evaluate the fossil palynological assemblage, combined with the calibration of the effects of temperature differences and lapse rates, a paleoelevation of 2700 +/- 200 m a.s.l. was estimated for the Hoh Xil Basin during the latest Eocene-early Oligocene, representing the height between the basin lake and the crests of the surrounding mountains.