It has been hypothesized that freezing of gait (FOG) in parkinsonian patients (PD) might be triggered by a breakdown in the normal symmetry of gait. In this study, we evaluated the relationship between asymmetry of gait and FOG and the effects of intensive treadmill treatment on asymmetry. We studied 30 patients with (FOG+) and 30 without (FOG-) freezing in "on" stage. Patients underwent a 4-week rehabilitation treatment using a treadmill with auditory and visual cues and were evaluated at enrollment and at the end of rehabilitation. Outcome measures were gait speed, stride length, asymmetry of gait, Six-minute walking test (6MWT), Unified Parkinson's Disease Rating Scale (UPDRS) II-III, Berg Balance Scale, Timed Up and Go Test, comfortable-fast gait speeds, freezing of gait questionnaire (FOGQ). At enrollment, no differences in gait parameters were observed between the two groups, which differed only in UPDRS_II and BBS. Both FOG+ and FOG- patients spent more time on the left foot (time on left/time on right foot 1.37, p = 0.002, 1.18, p = 0.016, respectively). Rehabilitation determined a homogeneous improvement in both groups of patients for all variables except UPDRS_II and balance, for which a better improvement was observed in FOG+ patients. The improvement in FOGQ in FOG+ patients was significantly correlated to the improvement in asymmetry of gait (Spearman R = 0.46, p = 0.013). Our data support a direct involvement of the asymmetry of gait in the development of FOG in PD. Treadmill training is effective in improving gait and balance in PD FOG+ patients and this might be related to a reduction of asymmetric gait.