Objective—Peripheral artery disease (PAD) is characterized by impaired blood flow to the lower extremities, causing claudication and exercise intolerance. The mechanism(s) by which exercise training improves functional capacity is not understood. This study tested the hypothesis that in PAD patients who undergo supervised exercise training, increases in capillary density (CD) in calf muscle take place before improvements in peak oxygen uptake (VO2). Methods and Results—Thirty-five PAD patients were randomly assigned to 12 weeks of directly supervised or home-based exercise training. Peak VO2 testing and gastrocnemius muscle biopsies were performed at baseline and after training. CD (endothelial cells/mm2) was measured using immunofluorescence staining. After 3 weeks of directly supervised training, patients had an increase in CD (216±66 versus 284±77, P<0.01) but no increase in peak VO2. However, after 12 weeks, peak VO2 increased (15.3±2.8 versus 16.8±3.8, P<0.01), whereas in muscle, CD remained increased over baseline, but there were no changes in markers of oxidative capacity. Within subjects, CD was related to peak VO2 before and after directly supervised training. Conclusion—Changes in CD in ischemic muscle with training may modulate the response to training, and those changes precede the increase in VO2.