Objective: The underlying pathobiology of the paradoxical relationship between obesity and adverse outcomes in coronary artery disease (CAD) is unclear. Our objective was to determine the association between obesity and circulating progenitor cell (CPC) counts—a measure of intrinsic regenerative capacity—in asymptomatic individuals and patients with CAD and its impact on the obesity paradox. Approach and Results: CPCs were enumerated by flow cytometry as CD45 ^med+ cells expressing CD34+, CD133+, and CXCR4+ epitopes in 672 asymptomatic individuals (50 years of age; 28% obese) and 1277 patients with CAD (66 years of age; 39% obese). The association between obesity and CPCs was analyzed using linear regression models. The association of obesity and CPCs with cardiovascular death/myocardial infarction events over 3.5-year follow-up in patients with CAD was studied using Cox models. Obesity was independently associated with 16% to 34% higher CPC counts (CD34+, CD34+/CD133+, and CD34+/CXCR4+) in asymptomatic individuals. This association was not attenuated by systemic inflammation, insulin resistance, or secretion but partly attenuated by cardiorespiratory fitness and body composition. In patients with CAD, obesity was associated with 8% to 12% higher CPC counts and 30% lower risk of adverse outcomes. Compared with nonobese patients, only obese patients with high CPC counts (CD34+ cells ≥median, 1806 cells/mL) were at a lower risk (hazard ratio, 0.52 [95% CI, 0.31–0.88]), whereas those with low counts (<median) were at a similar risk (hazard ratio, 0.75 [95% CI, 0.48–1.15]). Conclusions: Obesity is associated with higher CPC counts. The obesity paradox of improved outcomes with obesity in CAD is limited to patients with intact regenerative capacity who have high CPC counts.