Background: Gastric cancer (GC) is a major health burden worldwide, with half of patients developing metastases within 5 years after treatment, urging novel biomarkers for diagnosis and efficient therapeutic targeting. Sialyl-Lewis A (SLeA), a terminal glycoepitope of glycoproteins and glycolipids, offers tremendous potential towards this objective. It is rarely expressed in healthy tissues and blood cells, while it is present in highly metastatic cell lines and metastases. SLeA is also involved in E-selectin mediated metastasis, making it an ideal target to control disease dissemination. Methods and Results: To improve cancer specificity, we have explored the SLeA-glycoproteome of six GC cell models, with emphasis on glycoproteins showing affinity for E-selectin. A novel bioinformatics-assisted algorithm identified nucleolin (NCL), a nuclear protein, as a potential targetable biomarker potentially involved in metastasis. Several immunoassays, including Western blot and in situ proximity ligation reinforced the existence of cell surface NCL-SLeA glycoforms in GC. The NCL-SLeA glycophenotype was associated with decreased survival and was not reflected in relevant healthy tissues. Conclusions: NCL-SLeA is a biomarker of poor prognosis in GC holding potential for precise cancer targeting. This is the first report describing SLeA in preferentially nuclear protein, setting a new paradigm for cancer biomarkers discovery and targeted therapies.