Gastric cancer is a leading cause of death worldwide, and patients have an overall 5-year survival rate of less than 10%. Using quantitative proteomic techniques together with microarray chips, we have established comprehensive proteome and transcriptome profiles of the metastatic gastric cancer TMC-1 cells and the noninvasive gastric cancer SC-M1 cell. Our qualitative protein profiling strategy offers the first comprehensive analysis of the gastric cancer cell proteome, identifying 926 and 909 proteins from SC-M1 and TMC-1 cells, respectively. Cleavable isotope-coded affinity tagging analysis allows quantitation of a total of 559 proteins (with a protein false-positive rate of <0.005), and 240 proteins were differentially expressed (>1.3-fold) between the SC-M1 and TMC-1 cells. We identified numerous proteins not previously associated with gastric cancer. Notably, a large subset of differentially expressed proteins was associated with tumor metastasis, including proteins functioning in cell-cell and cell-extracellular matrix (cell-ECM) adhesion, cell motility, proliferation, and tumor immunity. Gene expression profiling by DNA microarray revealed differential expression (of >2-fold) of about 1000 genes. The weak correlation observed between protein and mRNA profiles highlights the important complementarities of DNA microarray and proteomics approaches. These comparative data enabled us to map the disease-perturbed cell-cell and cell-ECM adhesion and Rho GTPase-mediated cytoskeletal pathways. Further validation of a subset of genes suggests the potential use of vimentin and galectin 1 as markers for metastasis. We demonstrate that combining proteomic and genomic approaches not only provides a rapid, robust, and sensitive platform to elucidate the molecular mechanisms underlying gastric cancer metastasis but also may identify candidate diagnostic markers and therapeutic targets.