Circulating exosome holds great potentials as biomarker for diagnosis and prognosis of human cancers. Previously, we have applied small RNA sequencing to identify aberrantly expressed exosomal miRNAs as candidates for diagnostic markers in colon cancer patients. In this validation cohort, plasma derived exosomal miRNA was isolated from 50 early-stage colon cancer patients and 50 matched healthy volunteers. Real-time qRT-PCR revealed that miR-125a-3p, miR-320c were significantly up-regulated in plasma exosomes of the patients with early stage colon cancer. ROC curve showed that miR-125a-3p abundant level may predict colon cancer with an area of under the curve (AUC) of 68.5%, in comparison to that of CEA at 83.6%. Combination of miR-125a-3P and CEA improved the AUC to 85.5%. In addition, plasma exosome level of miR-125a-3p and miR-320c showed significant correlation with nerve infiltration (P < 0.01), but not with tumor size, infiltration depth, and differentiation degree (P > 0.05). On the contrary, plasma CEA level is correlated with tumor size, infiltration depth, and differentiation degree (P < 0.05, r = 0.3009-0.7270), but not with nerve infiltration (P = 0.744). In conclusion, this follow-up study demonstrated circulating plasma exosomal miR-125a-3p is readily accessible as diagnosis biomarker for early-stage colon cancer. When combined with conventional diagnostic markers, miR-125a-3p can improve the diagnostic power.