We report a proteomic analysis of microdissected material from formalin-fixed and paraffin-embedded colorectal cancer, quantifying >7500 proteins between patient matched normal mucosa, primary carcinoma, and nodal metastases. Expression levels of 1808 proteins changed significantly between normal and cancer tissues, a much larger fraction than that reported in transcript-based studies. Tumor cells exhibit extensive alterations in the cell-surface and nuclear proteomes. Functionally similar changes in the proteome were observed comparing rapidly growing and differentiated CaCo-2 cells. In contrast, there was minimal proteomic remodeling between primary cancer and metastases, suggesting that no drastic proteome changes are necessary for the tumor to propagate in a different tissue context. Additionally, we introduce a new way to determine protein copy numbers per cell without protein standards. Copy numbers estimated in enterocytes and cancer cells are in good agreement with CaCo-2 and HeLa cells and with the literature data. Our proteomic data set furthermore allows mapping quantitative changes of functional protein classes, enabling novel insights into the biology of colon cancer.