Phobic postural vertigo (PPV) is the most common cause of chronic dizziness in middle-aged patients. Many patients report symptoms involving gait. We investigated the gait performance and its relationship to the fear of falling and attention of PPV patients in a prospective study of 24 patients with PPV and 24 healthy subjects (HS) using a pressure-sensitive mat (GAITRite(®)). Subjects walked at three different speeds (slow, preferred, fast), both during cognitive dual tasks (DTc) and with eyes closed (EC). Falls efficacy and balance confidence were rated by the Falls Efficacy Scale-International (FES-I) and the Activities-specific Balance Confidence Scale (ABC). PPV patients walked slower, with reduced cadence (all p < 0.01), stride length (p < 0.05), and increased double support (p < 0.01) compared to HS. These changes correlated with FES-I (R = -0.528, p < 0.001) and ABC (R = 0.481, p < 0.01). Walking deterioration under DTc did not differ between PPV patients and HS, but patients showed a reduced cognitive processing speed (p < 0.05). When walking with EC, gait speed decreased more in PPV patients compared to HS (p < 0.05). Patients with PPV show gait changes which correlate with their fear of falling and balance confidence. Absent visual feedback leads to more pronounced gait deteriorations in PPV patients than in HS, indicating a higher reliance of patients on visual information during walking. These findings support the view that the gait characteristics of PPV can be attributed to an inadequate, cautious gait control.