Homeobox (HOX) gene family is known to be classic examples of the intimate relationship between embryogenesis and tumorigenesis. However, less is known about the involvement of HOX gene family with gastric cancerogenesis. Here, we screened the expression of HOX gene family in gastric cancers and explored the relationships between them by cDNA microarray. We found several differentially expressed HOX genes in gastric cancers, especially HOXA10 (11/12) and HOXA13 (11/12) with significantly higher expression in the cancerous tissues. Furthermore, we validated HOXA13 as a novel prognostic marker in gastric cancer based on immunohistochemistry and statistical analysis. HOXA13 expression was significantly up-regulated in cancerous tissues compared with the corresponding non-cancerous mucosa (P < 0.001). Up-expression of HOXA13 was significantly correlated with T stage (P = 0.002), M stage (P = 0.024), advanced UICC stage (P < 0.001), histological differentiation (P = 0.005), and relapse (P = 0.001). Patients with positive HOXA13 expression had a obviously lower overall survival (OS) and disease-free survival (DFS) rate than patients with negative HOXA13 expression (HR 3.331, 95 % CI 1.722-6.442, P < 0.001; HR 3.289, 95 % CI 1.703-6.351, P < 0.001, respectively). Univariate and multivariate Cox analysis confirmed that HOXA13 could serve as a significant independent prognostic factor for DFS and OS. Therefore, our results indicated that several HOX genes might be closely involved in the process of the gastric tumorigenesis. Furthermore, up-expression of HOXA13 might be associated with highly aggressive phenotype of gastric cancer. HOXA13 was a significant independent prognostic factor and could serve as a putative biomarker for diagnosis and prognosis of gastric cancer.