Abstract Background The aim of this pilot study was to identify proteins associated with advancement of colon cancer (CC). Methods A quantitative proteomics approach was used to determine the global changes in the proteome of primary colon cancer from patients with non-cancer normal colon (NC), non-adenomatous colon polyp (NAP), non-metastatic tumor (CC NM) and metastatic tumor (CC M) tissues, to identify up- and down-regulated proteins. Total protein was extracted from each biopsy, trypsin-digested, iTRAQ-labeled and the resulting peptides separated using strong cation exchange (SCX) and reverse-phase (RP) chromatography on-line to electrospray ionization mass spectrometry (ESI-MS). Results Database searching of the MS/MS data resulted in the identification of 2777 proteins which were clustered into groups associated with disease progression. Proteins which were changed in all disease stages including benign, and hence indicative of the earliest molecular perturbations, were strongly associated with spliceosomal activity, cell cycle division, and stromal and cytoskeleton disruption reflecting increased proliferation and expansion into the surrounding healthy tissue. Those proteins changed in cancer stages but not in benign, were linked to inflammation/immune response, loss of cell adhesion, mitochondrial function and autophagy, demonstrating early evidence of cells within the nutrient-poor solid mass either undergoing cell death or adjusting for survival. Caveolin-1, which decreased and Matrix metalloproteinase-9, which increased through the three disease stages compared to normal tissue, was selected to validate the proteomics results, but significant patient-to-patient variation obfuscated interpretation so corroborated the contradictory observations made by others. Conclusion Nevertheless, the study has provided significant insights into CC stage progression for further investigation.