This investigation examined effects of climate change, measured as annual, seasonal, and monthly air temperature and precipitation from 1958 to 2010, on water resources (i.e., runoff) in the Bosten Lake Basin. Additionally, teleconnections of hydrological changes to large-scale circulation indices including El Nino Southern Oscillation (ENSO), Arctic Oscillation (AO), North Atlantic Oscillation (NAO), Tibetan High (XZH), westerly circulation index (WI), and northern hemisphere polar vortex area index (VPA) were analyzed in our study. The results showed the following. (1) Annual and seasonal air temperature increased significantly in the Bosten Lake Basin. Precipitation exhibited an increasing trend, while the significance was less than that of temperature. Abrupt changes were observed in 1996 in mountain temperature and in 1985 in plain temperature. (2) Runoff varied in three stages, decreasing before 1986, increasing from 1987 to 2003, and decreasing after 2003. (3) Precipitation and air temperature have significant impacts on runoff. The hydrological processes in the Bosten Lake Basin were (statistically) significantly affected by the northern hemisphere polar vortex area index (VPA) and the Tibetan High (XZH). The results of this study are good indicators of local climate change, which can enhance human mitigation of climate warming in the Bosten Lake Basin.