Background: Although both capillary density and peak VO2 improve with exercise training, it is difficult to find a relationship between these two measures. It has been suggested that peak VO₂ may be more related to central hemodynamics than to the oxidative potential of skeletal muscle which may account for this observation. We hypothesized that change in a measure of sub-maximal performance, anaerobic threshold, might be related to change in skeletal muscle capillary density, a marker of oxidative potential in muscle, with training. Due to baseline differences among these variables, we also hypothesized that relationships might be gender specific . Methods: A group of 21 subjects completed an inactive control period while 28 subjects (17 men and 11 women) participated in a six month high intensity exercise program. All subjects were sedentary, overweight and dyslipidemic. Potential relationships were assessed between change in capillary density with both change in VO₂ at peak and at anaerobic threshold with exercise training. All variables and relationships were assessed for gender specific effects. Results: Change in peak VO₂ was not related to change in capillary density after exercise training in either gender. Men had a positive correlation between change in VO₂ at anaerobic threshold and change in capillary density with exercise training (r = 0.635, p <0.01) while women had an inverse relationship (r = -0.636, p < 0.05) between the change in these variables. Conclusions: These findings suggest that while enhanced capillary density is associated with training-induced improvements in sub-maximal performance in men, this relationship is different in women.