A majority of early colorectal cancers (CRCs) with submucosal invasion undergo surgical operation, despite a very low incidence of lymph node metastasis. Our study aimed to identify microRNAs (miRNAs) specifically responsible for lymph node metastasis in submucosal CRCs. MicroRNA microarray analysis revealed that miR-100 and miR-125b expression levels were significantly lower in CRC tissues with lymph node metastases than in those without metastases. These results were validated by quantitative real-time PCR in a larger set of clinical samples. The transfection of a miR-100 or miR-125b inhibitor into colon cancer HCT116 cells significantly increased cell invasion, migration, and MMP activity. Conversely, overexpression of miR-100 or miR-125b mimics significantly attenuated all these activities but did not affect cell growth. To identify target mRNAs, we undertook a gene expression array analysis of miR-100-silenced HCT116 cells as well as negative control cells. The Ingenuity Pathway Analysis, TargetScan software analyses, and subsequent verification of mRNA expression by real-time PCR identified mammalian target of rapamycin (mTOR) and insulin-like growth factor 1 receptor (IGF1R) as direct, and Fas and X-linked inhibitor-of-apoptosis protein (XIAP) as indirect candidate targets for miR-100 involved in lymph node metastasis. Knockdown of each gene by siRNA significantly reduced the invasiveness of HCT116 cells. These data clearly show that downregulation of miR-100 and miR-125b is closely associated with lymph node metastasis in submucosal CRC through enhancement of invasion, motility, and MMP activity. In particular, miR-100 may promote metastasis by upregulating mTOR, IGF1R, Fas, and XIAP as targets. Thus, miR-100 and miR-125b may be novel biomarkers for lymph node metastasis of early CRCs with submucosal invasion.