Prostate cancer is a clinically heterogeneous disease, ranging from indolent asymptomatic disease to very aggressive metastatic and life threatening forms of the disease. Distant metastasis represents the major lethal cause of prostate cancer. The most critical clinical challenge in the management of the patients is identifying those individuals at risk of developing metastatic disease. To understand the molecular mechanisms of prostate cancer metastasis and identify markers with metastatic potential, we have analyzed protein expression in two syngeneic prostate cancer cells lines PC3-N2 and PC3-ML2 using isobaric tags for relative and absolute quantitation labeling and multi-dimensional protein identification technology liquid chromatography matrix assisted laser desorption ionization tandem mass spectrometry. PC3-N2 is lowly metastatic while PC3-ML2 highly metastatic. A total of 1,756 proteins were identified in the analyses with 130 proteins showing different expression levels (p<0.01) in the two cell lines. Out of these, 68 proteins were found to be significantly up-regulated while 62 are significantly down-regulated in PC3-ML2 cells compared with PC3-N2 cells. The upregulation of plectin and vimentin which were the most significantly differentially expressed were validated by Western blot and their functional relevance with respect to invasion and migration was determined by siRNA gene silencing. To our knowledge, this study is the first to demonstrate that up-regulation of vimentin and plectin expression positively correlates with the invasion and metastasis of androgen-independent PCA.