Gait impairment resulting in loss of mobility is a major cause of disability in Parkinson's disease, and current therapy including levodopa, surgery and rehabilitation are inadequate to preserve mobility as PD progresses. This study will compare the efficacy of 3 exercise regimens for gait-related disability: 1) treadmill training with aerobic exercise, 2) treadmill training without aerobic exercise, and 3) stretching and resistance (muscle strengthening) exercise. Efficacy will be based on both motor (fitness, gait, mobility) and non-motor (depression, fatigue, quality of life) outcomes. The results of this study will also help us understand the mechanism of efficacy of exercise, by comparing 3 approaches with different proportions of 3 potential mechanisms: 1) aerobic conditioning, 2) gait-retraining and 3) musculoskeletal conditioning. This study is important because it tests the efficacy of exercise programs that are widely available, to improve gait impairment, one of the most disabling symptoms of PD.