This study aimed to investigate the relationship between supervised exercise training (SET)-induced changes in treadmill performance and 6 min walking distance, and changes in general (physical and mental) self-perceived health-related quality of life (HRQoL) in symptomatic patients with lower extremity peripheral artery disease (PAD). This is an observational study investigating Fontaine stage II PAD patients participating in 3-month SET. Before and following SET, treadmill performance (pain-free (PFWD) and maximal (MWD)), and 6 min walking distance (6MWD) were assessed. Self-perceived HRQoL was assessed with the Medical Outcomes Study Short-Form 36 (SF-36). Ankle- and toe-brachial indexes were also measured. One-hundred forty-seven patients with PAD were included (64.9 ± 9.6 y, 70% men). After SET, PFWD (+102%, p ≤ 0.001), MWD (+87%, p ≤ 0.001), and 6MWD (+14%, p ≤ 0.001) significantly increased. All eight SF-36 subscale scores significantly improved following SET (p ≤ 0.04). SET significantly improved physical and mental component summaries of the SF-36 (p ≤ 0.001). Larger increases in 6MWD were associated with greater improvements in physical (β = 0.19; p = 0.02) and mental (β = 0.24; p = 0.005) component summaries of the SF-36. No significant relationship was observed between changes in treadmill performance and changes in physical and mental component summaries of the SF-36. These results show that improvements in 6MWD following SET are related to improvements in general self-perceived HRQoL in patients with symptomatic lower extremity PAD. On the contrary, changes in treadmill performance were not related to improvements in HRQoL. These results suggest that the 6 min walking test is an essential outcome measure to assess overall patient functional status following interventions in patients with PAD.