Cancer stem cells (CSCs) are responsible for cancer progression, metastasis, and recurrence. To date, the specific markers of CSCs remain undiscovered. The aim of this study was to identify novel biomarkers of gastric CSCs for clinical diagnosis using proteomics technology. CSC-like SP cells, OCUM-12/SP cells, OCUM-2MD3/SP cells, and their parent OCUM-12 cells and OCUM-2MD3 cells were used in this study. Protein lysates from each cell line were analyzed using QSTAR Elite Liquid Chromatography with Tandem Mass Spectrometry, coupled with isobaric tags for relative and absolute quantitation technology. Candidate proteins detected by proteomics technology were validated by immunohistochemical analysis of 300 gastric cancers. Based on the results of LC-MS/MS, eight proteins, including RBBP6, GLG1, VPS13A, DCTPP1, HSPA9, HSPA4, ALDOA, and KRT18, were up-regulated in both OCUM-12/SP cells and OCUM-2MD3/SP cells when compared to their corresponding parent cells. RT-PCR analysis indicated that the expression level of RBBP6, HSPA4, DCTPP1, HSPA9, VPS13A, ALDOA, GLG1, and CK18 was high in OCUM-12/SP and OCUM-2MD3/SP, in compared with the control of parent OCUM-12 and OCUM-2MD3. These proteins were significantly associated with advanced invasion depth, lymph node metastasis, distant metastasis, or advanced clinical stage. RBBP6, DCTPP1, HSPA4, and ALDOA expression in particular were significantly associated with a poor prognosis in the 300 gastric cancer patients. RBBP6 was determined to be an independent prognostic factor. The motility-stimulating ability of OCUM-12/SP cells and OCUM-2MD3/SP cells was inhibited by RBBP6 siRNA. These findings might suggest that the eight proteins, RBBP6, GLG1, VPS13A, DCTPP1, HSPA9, HSPA4, ALDOA, and KRT18, utilizing comparative proteomics analysis, were perceived to be potential CSC markers of gastric cancer. Of the eight candidate proteins, RBBP6 was suggested to be a promising prognostic biomarker and a therapeutic target for gastric cancer.