Physiological and/or pathological implications of the dynamics of sleep stage transitions have not, to date, been investigated. We report detailed duration and transition statistics between sleep stages in healthy subjects and in others with chronic fatigue syndrome (CFS); in addition, we also compare our data with previously published results for rats. Twenty-two healthy females and 22 female patients with CFS, characterized by complaints of unrefreshing sleep, underwent one night of polysomnographic recording. We find that duration of deep sleep (Stages III and IV) follows a power-law probability distribution function; in contrast, Stage II sleep durations follow a stretched exponential and Stage I and REM sleep durations follow an exponential function. These stage duration distributions show a gradually increasing departure from the exponential form with increasing depth of sleep towards a power-law type distribution for deep sleep, suggesting increasing complexity of regulation of deeper sleep stages. We also find a substantial number of REM to non-REM sleep transitions in humans, while this transition is reported to be virtually non-existent in rats. The relative frequency of this REM to non-REM sleep transition is significantly lower in CFS than in controls, resulting in a significantly greater relative transition frequency of from both REM and Stage I sleep to awake. Such an alteration in the transition pattern suggests that the normal continuation of sleep in light or REM sleep is disrupted in CFS. We conclude that dynamic transition analysis of sleep stages is useful for elucidating yet-to-be-determined human sleep regulation mechanisms with pathophysiological implications.