This study examined the ways in which gait patterns and physiological rhythms such as those of muscle activity (tibialis anterior (TA) and biceps femoris (BF)) and cardiac activity are affected by the fatigue induced by prolonged free walking. Twelve normal subjects who walked for 3 h at their preferred pace were divided into two groups according to whether their mean gait cycle time (reciprocal of stride rate) during the second 90 min was higher (Group A: n=8) or lower (Group B: n=4) than that during the first 90 min. For Group A, the level of subjective fatigue during the walking task was significantly higher and the heart rate at rest was significantly lower than Group B. In Group A, prolonged walking significantly decreased the mean power frequency of the electromyography from TA, increased the variability of gait rhythm, decreased the largest Lyapunov exponent of the vertical component of back-waist acceleration, and decreased the amplitude of the vertical component of back-waist acceleration. Taking the onset timings of these changes into account, we propose that subjects who tire easily during prolonged walking first show local muscle fatigue at TA followed by instability of gait rhythm and then they slow their gait rhythm to enhance local dynamic stability. For both groups we constructed a physical fatigue index described by linear regression of gait and physiological variables. When we compared the subjective fatigue level with the fatigue level predicted using the index, we obtained a relatively high correlation coefficient for both groups (r=0.77).