Background: Several biologically plausible mechanisms have been proposed to mediate the association between periodontitis and atherosclerotic vascular disease (AVD), including adverse effects on vascular endothelial function. Circulating endothelial progenitor cells (cEPCs) are known to contribute to vascular repair, but limited data are available regarding the relationship between cEPC levels and periodontitis. The aims of this cross-sectional study are to investigate the levels of hemangioblastic and monocytic cEPCs in patients with periodontitis and periodontally healthy controls and to associate cEPC levels with the extent and severity of periodontitis. Methods: A total of 112 individuals (56 patients with periodontitis and 56 periodontally healthy controls, aged 26 to 65 years; mean age: 43 years) were enrolled. All participants underwent a full-mouth periodontal examination and provided a blood sample. Hemangioblastic cEPCs were assessed using flow cytometry, and monocytic cEPCs were identified using immunohistochemistry in cultured peripheral blood mononuclear cells. cEPC levels were analyzed in the entire sample, as well as in a subset of 50 pairs of patients with periodontitis/periodontally healthy controls, matched with respect to age, sex, and menstrual cycle. Results: Levels of hemangioblastic cEPCs were approximately 2.3-fold higher in patients with periodontitis than periodontally healthy controls, after adjustments for age, sex, physical activity, systolic blood pressure, and body mass index (P = 0.001). A non-significant trend for higher levels of monocytic cEPCs in periodontitis was also observed. The levels of hemangioblastic cEPCs were positively associated with the extent of bleeding on probing, probing depth, and clinical attachment loss. Hemangioblastic and monocytic cEPC levels were not correlated (Spearman correlation coefficient 0.03, P = 0.77), suggesting that they represent independent populations of progenitor cells. Conclusion: These findings further support the notion that oral infections have extraoral effects and document that periodontitis is associated with a mobilization of EPCs from the bone marrow, apparently in response to systemic inflammation and endothelial injury.