This paper attempted to identify fractal and chaotic characteristics of the annual runoff processes in headwaters of the Tarim River. Methods of fractal analyses were used to explore several aspects of the temporal changes from 1957 to 2002. The main findings are as follows: (1) The annual runoff processes of the three headwaters of the Tarim River are complex nonlinear systems with fractal as well as chaotic dynamics. (2) The correlation dimensions of attractor derived from the time series of the annual runoff for the Hotan, Yarkand and Aksu rivers are all greater than 3.0 and non-integral, implying that all three rivers are chaotic dynamical systems that are sensitive to initial conditions, and the dynamic modeling of their annual runoff process requires at least four independent variables. (3) The time series of annual runoff in each river presents a long-term correlation characteristic. The Hurst exponent for the period of 1989 to 2002 suggests that we may expect to see an increasing trend in the annual runoff of the Aksu and Yarkand rivers in the years after 2002, but a decreasing tendency for the Hotan River in the same period.