Nonlinear characteristics of the runoff processes in the headwaters of the Tarim River were identified and evaluated using several selected methods, including wavelet analysis, correlation dimension, and R/S analysis. Time-series of annual data describing runoff, average temperature, and precipitation from 1957 to 2005 were used to construct and test empirical models. The primary findings of this study were as follows: (1) The annual runoff of the headwaters are complex and nonlinear in nature, and they each presented periodic, nonlinear trends at the chosen time scales, chaotic dynamics, and long-memory characteristics. (2) These nonlinear trends appeared to have resulted from the regional climatic changes that occurred during the study period. The periodicity of changes in runoff occurred on an approximately 25-year cycle, which appeared to be correlated with temperature and precipitation cycles. In addition, the annual runoff exhibited a significant, positive correlation with the temperature and precipitation factors at the 4-, 8-, 16-, and 32-year temporal scales. (3) The correlation dimensions of the attractor derived from the runoff time series for the Hotan, Yarkand, and Aksu rivers were all greater than 3.0 and non-integral, implying that all three rivers are dynamic chaotic systems that are sensitive to initial conditions, and that the dynamic modeling of their annual runoff requires at least four independent variables. (4) The computed Hurst exponents indicate that a long-term memory characteristic exists in the annual runoff processes. However, there were some differences observed, with the Aksu and Yarkand rivers demonstrating a persistent trait, and the Hotan River exhibiting an anti-persistent feature.