Despite the discovery of numerous driving and passenger genes that play key roles in cancer characteristics, progress in cancer treatment has not been satisfactory. This is mainly because conventional therapies are neither selective nor targeted. Another important reason is that cancer cells rapidly develop resistance to chemotherapeutic agents due to excessive accumulation of mutations and/or epigenetic changes. In light of this, we believe that the discovery of new targets and key genes/proteins could improve treatment options. In this study, tissue samples (tumor and normal mucosa) were first collected from the colon or rectum by right or left hemicolectomy. Proteomic analysis was then performed using the label-free nLC-MS/MS method. We determined 77 proteins with statistically significant differences in expression levels between cancerous and normal mucosa. While the expression of 76 proteins was decreased in cancer tissues, only one protein (RNA-binding motif protein_X chromosome—RBMX) was increased in colorectal cancer tissues. The bioinformatics portal Metascape was used to determine the biological processes involved. 77 proteins with significantly different expression between cancerous and normal tissues were compared with the UALCAN platform using data from the Clinical Proteomics Tumor Analysis Consortium (CPTAC). The results for 45 of the 77 proteins clearly matched the CPTAC dataset. Western blot studies confirmed that RBMX protein (critical for gene transcription and alternative splicing of various pre-mRNAs) was increased 2.04-fold, while decorin protein (a matrix proteoglycan with tumor suppressor functions) was dramatically decreased by about 6.04-fold in tumor samples compared with normal mucosa.