Colorectal adenocarcinoma is one of the worldwide leading causes of cancer deaths. Discovery of specific biomarkers for early detection of cancer progression and the identification of underlying pathogenetic mechanisms are important tasks. Global proteomic approaches have thus far been limited by the large dynamic range of molecule concentrations in tissues and the lack of selective enrichment of the low-abundance proteome. We studied paired cancerous and normal clinical tissue specimens from patients with colorectal adenocarcinomas by heparin affinity fractionation enrichment (HAFE) followed by 2-D PAGE and tandem mass spectrometric (MS/MS) identification. Fifty-six proteins were found to be differentially expressed, of which 32 low-abundance proteins were only detectable after heparin affinity enrichment. MS/MS was used to identify 5 selected differentially expressed proteins as proteasome subunit beta type 7 (PSB7), hemoglobin alpha subunit (HBA), peroxiredoxin-1 (PRDX1), argininosuccinate synthase (ASSY), and signal recognition particle 9 kDa protein (SRP9). This is the first proteomic study detecting the differential expression of these proteins in human colorectal cancer tissue. Several of the proteins are functionally related to tissue hypoxia and hypoxic adaptation. The relative specificities of PSB7, PRDX1, and SRP9 overexpression in colon cancer were investigated by Western blot analysis of patients with colon adenocarcinomas and comparison with a control cohort of patients with lung adenocarcinomas. Furthermore, immunohistochemistry on tissue sections was used to define the specific locations of PSB7, PRDX1, and SRP9 up-regulation within heterogeneous primary human tumor tissue. Overexpression of the three proteins was restricted to the neoplastic cancer cell population within the tumors, demonstrating both cytoplasmic and nuclear localization of PSB7 and predominantly cytoplasmic localization of PRDX1 and SRP9. In summary, we describe heparin affinity fractionation enrichment (HAFE) as a prefractionation tool for the study of the human primary tissue proteome and the discovery of PSB7, PRDX1, and SRP9 up-regulation as candidate biomarkers of colon cancer.