Screening aimed at the evaluation of the presence of small RNAs with anticancer properties in three mushrooms species, besides Boletus edulis, namely Boletus spretus (current name Baorangia emilei), Boletus pinophilus and Cantharellus cibarius, was conducted. All mushrooms yielded an ethanol insoluble and water soluble small RNA fraction purified from co-extracted polysaccharides by anion-exchange chromatography. Small RNAs from B. spretus and C. cibarius showed strong antiproliferative activity against human colon adenocarcinoma cell lines (IC50 of 5.6 μg mL−1 and 11.1 μg mL−1 for LS180 and 1.9 μg mL−1 and 12.6 μg mL−1 for HT-29 cell lines, respectively) while those isolated from B. pinophilus showed a much lower antiproliferative activity in these cells. All RNA fractions were nontoxic against CCD841 CoTr human colon epithelial cells. A detailed study of the anticancer mechanism of C. cibarius small RNAs showed that their antiproliferative activity was due to p53-dependent cell cycle arrest mediated by p21, while the proapoptotic effect was mostly dependent on the enhancement of p53 expression. Overall, small RNA fractions isolated from some edible mushrooms, namely C. cibarius, show potent antiproliferative activity without cytotoxicity to normal cells, being a potential new anticancer agent naturally present in mushrooms that we eat.