The nonlinear trend of runoff and its response to climate change in the Aksu River were identified and evaluated using several selected methods, including grey relation analysis, wavelet analysis, and regression analysis. The time series of runoff and related climate variables from two hydrologic stations and four meteorological stations during 1959–2005 for the Aksu River were used to construct and test empirical models. The key findings of this study indicate that although the time series of the runoff, temperature and precipitation present nonlinear trends, the runoff exhibits a linear correlation with the temperature and precipitation. These results reveal that there is a close relationship between variations in the annual runoff of the Aksu River and regional climate change; in other words, the nonlinear trends of the variations in the runoff is the response to that of regional climate change. The details supporting the key findings are as follows: (1) The annual runoff presented nonlinear trends that depend on time scales, which appeared to have resulted from the regional climate changes that occurred during the study period. (2) The periodicity of changes in runoff, temperature, and precipitation are closely correlated, that of annual runoff occurred on 24-year cycle, whereas annual average temperature and annual precipitation occurred on 23-and 25-year cycles. (3) The annual runoff exhibited a significant, positive correlation with the temperature and precipitation at the 1-, 2-, 4-, and 8-year temporal scales.