This paper applied an integrated method combining grey relation analysis, wavelet analysis and statistical analysis to study climate change and its effects on runoff of the Kaidu River at multi-time scales. Major findings are as follows: 1) Climatic factors were ranked in the order of importance to annual runoff as average annual temperature, average temperature in autumn, average temperature in winter, annual precipitation, precipitation in flood season, average temperature in summer, and average temperature in spring. The average annual temperature and annual precipitation were selected as the two representative factors that impact the annual runoff. 2) From the 32-year time scale, the annual runoff and the average annual temperature presented a significantly rising trend, whereas the annual precipitation showed little increase over the period of 1957–2002. By changing the time scale from 32-year to 4-year, we observed nonlinear trends with increasingly obvious oscillations for annual runoff, average annual temperature, and annual precipitation. 3) The changes of the runoff and the regional climate are closely related, indicating that the runoff change is the result of the regional climate changes. With time scales ranging from 32-year, 16-year, 8-year and to 4-year, there are highly significant linear correlations between the annual runoff and the average annual temperature and the annual precipitation.