Parkinsons disease (PD) impairs movement and gait timing. Parkinsons gait consists of random disconnected strides, whereas stride times in healthy gait have a 1/f fractal structure. Fixed-tempo Rhythmic Auditory Stimulation (RAS) improves many aspects of gait timing, but stride-times become less correlated. In this experiment, PD patients and healthy participants walked with a) no auditory stimulation; b) fixed-tempo RAS; and c) an interactive rhythmic auditory stimulation computer system that used foot sensors and nonlinear oscillators to track and interact with the humans timing. Patients effortlessly synchronized with the interactive system, and their fractal scaling returned to levels of healthy participants. When patients and healthy participants did synchronize with the fixed-tempo RAS, their fractal scaling declined away from healthy 1/f levels. Higher fractal scaling persisted after interactive rhythmic stimulation indicating that internal rhythms stabilized. Interactive rhythmic auditory stimulation represents a promising rehabilitation tool to improve PD patients mobility and wellbeing.