Functional impairment of endothelial colony-forming cells (ECFCs), a specific cell lineage of endothelial progenitor cells (EPCs) is highly associated with the severity of coronary artery disease (CAD), the most common type of cardiovascular disease (CVD). Emerging evidence show that circulating microRNAs (miRNAs) in CAD patients’ body fluid hold a great potential as biomarkers. However, our knowledge of the role of circulating miRNA in regulating the function of ECFCs and the progression of CAD is still in its infancy. We showed that when ECFCs from healthy volunteers were incubated with conditioned medium or purified exosomes of cultured CAD ECFCs, the secretory factors from CAD ECFCs dysregulated migration and tube formation ability of healthy ECFCs. It is known that exosomes influence the physiology of recipient cells by introducing RNAs including miRNAs. By using small RNA sequencing (smRNA-seq), we deciphered the circulating miRNome in the plasma of healthy individual and CAD patients, and found that the plasma miRNA spectrum from CAD patients was significantly different from that of healthy control. Interestingly, smRNA-seq of both healthy and CAD ECFCs showed that twelve miRNAs that had a higher expression in the plasma of CAD patients also showed higher expression in CAD ECFCs when compared with healthy control. This result suggests that these miRNAs may be involved in the regulation of ECFC functions. For identification of potential mRNA targets of the differentially expressed miRNA in CAD patients, cDNA microarray analysis was performed to identify the angiogenesis-related genes that were down-regulated in CAD ECFCs and Pearson’s correlation were used to identify miRNAs that were negatively correlated with the identified angiogenesis-related genes. RT-qPCR analysis of the five miRNAs that negatively correlated with the down-regulated angiogenesis-related genes in plasma and ECFC of CAD patients showed miR-146a-5p and miR-146b-5p up-regulation compared to healthy control. Knockdown of miR-146a-5p or miR-146b-5p in CAD ECFCs enhanced migration and tube formation activity in diseased ECFCs. Contrarily, overexpression of miR-146a-5p or miR-146b-5p in healthy ECFC repressed migration and tube formation in ECFCs. TargetScan analysis showed that miR-146a-5p and miR-146b-5p target many of the angiogenesis-related genes that were down-regulated in CAD ECFCs. Knockdown of miR-146a-5p or miR-146b-5p restores CAV1 and RHOJ levels in CAD ECFCs. Reporter assays confirmed the direct binding and repression of miR-146a-5p and miR-146b-5p to the 3’-UTR of mRNA of RHOJ, a positive regulator of angiogenic potential in endothelial cells. Consistently, RHOJ knockdown inhibited the migration and tube formation ability in ECFCs. Collectively, we discovered the dysregulation of miR-146a-5p/RHOJ and miR-146b-5p/RHOJ axis in the plasma and ECFCs of CAD patients that could be used as biomarkers or therapeutic targets for CAD and other angiogenesis-related diseases.