Background Circulating progenitor cells (CPCs) improve cardiovascular function and organ perfusion by enhancing the capacities of endothelial repair and neovasculogenesis. This study investigates whether exercise regimens with/without hypoxia affect cardiac and muscular hemodynamics by modulating CPCs and angiogenic factors. Methods Forty sedentary males were randomly divided into hypoxic (HT, n = 20) and normoxic (NT, n = 20) training groups. The subjects were trained on a bicycle ergometer at 60%VO2max under 15% (HT) or 21% (NT) O2 conditions for 30 min daily, five days weekly for five weeks. Results After the five-week interventions, the HT group exhibited a larger improvement in aerobic capacity than the NT group. Furthermore, the HT regimen (i) enhanced cardiac output (QH) and perfusion (Q M)/oxygenation of vastus lateralis during exercise; (ii) increased levels of CD34+/KDR+/CD117+, CD34 +/KDR+/CD133+, and CD34+/KDR +/CD31+ cells in blood; (iii) promoted the proliferative capacity of these CPC subsets, and (iv) elevated plasma nitrite/nitrate, stromal cell-derived factor-1 (SDF-1), matrix metalloproteinase-9 (MMP-9), and vascular endothelial growth factor-A (VEGF-A) concentrations. Despite the lack of changes in QH and the number or proliferative capacity of CD34 +/KDR+/CD117+ or CD34+/KDR +/CD31+ cells, the NT regimen elevated both QM and plasma nitrite/nitrate levels and suppressed the shedding of endothelial cells (CD34-/KDR+/phosphatidylserine+ cells). Conclusions The HT regimen improves cardiac and muscular hemodynamic adaptations, possibly by promoting the mobilization/function of CPCs and the production of angiogenic factors. © 2013 Elsevier Ireland Ltd.