Osteogenic endothelial progenitor cells (EPCs) contribute to impaired endothelial repair and promote coronary artery disease (CAD) and vascular calcification. Immature EPCs expressing osteocalcin (OCN) has been linked to unstable CAD; however, phenotypic regulation of OCN-expressing EPCs is not understood. We hypothesized that gut-microbiome derived pro-inflammatory substance, trimethylamine N-oxide (TMAO) might be associated with mobilization of OCN-expressing EPCs. This study aimed to investigate the association between dysbiosis, TMAO, and circulating mature and immature OCN-expressing EPCs levels in patients with and without CAD. We included 202 patients (CAD N = 88; no CAD N = 114) who underwent assessment of EPCs using flow cytometry and gut microbiome composition. Mature and immature EPCs co-staining for OCN were identified using cell surface markers as CD34+/CD133-/kinase insert domain receptor (KDR)+ and CD34-/CD133+/KDR+ cells, respectively. The number of observed operational taxonomy units (OTU), index of microbial richness, was used to identify patients with dysbiosis. The number of immature OCN-expressing EPCs were higher in patients with CAD or dysbiosis than patients without. TMAO levels were not associated with circulating levels of OCN-expressing EPCs. The relative abundance of Ruminococcus gnavus was moderately correlated with circulating levels of immature OCN-expressing EPCs, especially in diabetic patients. Gut dysbiosis was associated with increased levels of TMAO, immature OCN-expressing EPCs, and CAD. The relative abundance of Ruminococcus gnavus was correlated with immature OCN-expressing EPCs, suggesting that the harmful effects of immature OCN-expressing EPCs on CAD and potentially vascular calcification might be mediated by gut microbiome-derived systemic inflammation.