We compare the complexity of human gait time series from healthy subjects under different conditions. Using the recently developed multiscale entropy algorithm, which provides a way to measure complexity over a range of scales, we observe that normal spontaneous walking has the highest complexity when compared to slow and fast walking and also to walking paced by a metronome. These findings have implications for modeling locomotor control and for quantifying gait dynamics in physiologic and pathologic states.