Colorectal cancer (CRC) is a disease with high incidence and mortality. Colonoscopy is a gold standard among tests used for CRC traceability. However, serious complications, such as colon perforation, may occur. Non-invasive diagnostic procedures are an unmet need. We aimed to identify a plasma microRNA (miRNA) signature for CRC detection. Plasma samples were obtained from subjects (n = 109) at different stages of colorectal carcinogenesis. The patients were stratified into a non-cancer (27 healthy volunteers, 17 patients with hyperplastic polyps, 24 with adenomas), and a cancer group (20 CRC and 21 metastatic CRC). miRNAs (381) were screened by TaqMan Low-Density Array. A classifier based on four differentially expressed miRNAs (miR-28-3p, let-7e-5p, miR-106a-5p, and miR-542-5p) was able to discriminate cancer versus non-cancer cases. The overexpression of these miRNAs was confirmed by RT-qPCR, and a cross-study validation step was implemented using eight data series retrieved from Gene Expression Omnibus (GEO). In addition, another external data validation using CRC surgical specimens from The Cancer Genome Atlas (TCGA) was carried out. The predictive model’s performance in the validation set was 76.5% accuracy, 59.4% sensitivity, and 86.8% specificity (area under the curve, AUC = 0.716). The employment of our model in the independent publicly available datasets confirmed a good discrimination performance in five of eight datasets (median AUC = 0.823). Applying this algorithm to the TCGA cohort, we found 99.5% accuracy, 99.7% sensitivity, and 90.9% specificity (AUC = 0.998) when the model was applied to solid colorectal tissues. Overall, we suggest a novel signature of four circulating miRNAs, i.e., miR-28-3p, let-7e-5p, miR-106a-5p, and miR-542-5p, as a predictive tool for the detection of CRC.