Quaternary records of climate change from terrestrial sources, such as lake sediments and aeolian sediments, in general agree well with marine records. But continuous records that cover more than the past one million years were essentially unavailable until recently, when the high-sedimentation-rate site of Lake Baikal was exploited. Because of its location in the middle latitudes, Lake Baikal is highly sensitive to insolation changes and the entire lake remained uncovered by ice sheets throughout the Pleistocene epoch, making it a valuable archive for past climate. Here we examine long sediment cores from Lake Baikal that cover the past 12 million years. Our record reveals a gradual cooling of the Asian continental interior, with some fluctuations. Spectral analyses reveal periods of about 400 kyr, 600 kyr and 1,000 kyr, which may correspond to Milankovitch periods (reflecting orbital cycles). Our results indicate that changes in insolation were closely related to long-term environmental variations in the deep continental interior, over the past 12 million years.