Arid Central Asia (ACA) lies on a major climatic boundary between the mid-latitude westerlies and the northwestern limit of the Asian summer monsoon, yet only a few high-quality reconstructions exist for its climate history. Here we calibrate a new organic geochemical proxy for lake temperature, and present a 45-yr-resolution temperature record from Hurleg Lake at the eastern margin of the ACA in the northern Tibetan Plateau. Combination with other proxy data from the same samples reveals a distinct warm-dry climate association throughout the record, which contrasts with the warm-wet association found in the Asian monsoon region. This indicates that the climatic boundary between the westerly and the monsoon regimes has remained roughly in the same place throughout the Holocene, at least near our study site. Six millennial-scale cold events are found within the past 9000 yr, which approximately coincide with previously documented events of northern high-latitude cooling and tropical drought. This suggests a connection between the North Atlantic and tropical monsoon climate systems, via the westerly circulation. Finally, we also observe an increase in regional climate variability after the mid-Holocene, which we relate to changes in vegetation (forest) cover in the monsoon region through a land-surface albedo feedback.