Gastric cancer is the second most common cause of cancer-related mortality worldwide. Accurate prediction of disease progression is difficult, and new biomarkers for clinical use are essential. Recently, we reported that the proteasome-associated deubiquitinating enzyme UCHL5/Uch37 is a new prognostic marker in both rectal cancer and pancreatic ductal adenocarcinoma. Here, we have assessed by immunohistochemistry UCHL5 tumor expression in gastric cancer. The study cohort comprised 650 patients, who underwent surgery in Helsinki University Hospital, Finland, between 1983 and 2009. We investigated the association of cytoplasmic UCHL5 tumor expression to assess clinicopathological parameters and patient survival. Positive cytoplasmic UCHL5 tumor immunoexpression is linked to increased survival of patients with small (<5 cm) tumors (p = 0.001), disease stages I-II (p = 0.025), and age 66 years or older (p = 0.037). UCHL5 is thus a potential marker in gastric cancer with new prognostic relevance.