MicroRNAs (miRNAs) are known to drive the pathogenesis of colorectal cancer (CRC) via the regulation of cancer stem cells (CSCs). We studied the miRNA expression profile of primary CSCs isolated from patients with CRC (pCRCSCs). Compared to pCRCSC-derived differentiated cells, 98 differentially expressed miRNAs were identified in pCRCSCs. Target genes encoding pCRCSC-related miRNAs were identified using a combination of miRNA target databases and miRNA-mRNA regulatory networks from the same patient. The pCRCSC-related miRNA target genes were associated with pathways contributing to malignant phenotypes, including I-kappa B kinase/NF-kappa B signaling, signal transduction by p53 class mediator, Ras signaling, and cGMP-PKG signaling. The pCRCSC-related miRNA expression signature was independently associated with poor overall survival in both the training and validation cohorts. We have thus identified several pCRCSC-related miRNAs with oncogenic potential that could serve as prognostic biomarkers for CRC.