Background: Nuclear factor-κB (NF-κB) and vascular endothelial growth factor (VEGF) are involved in cell proliferation, invasion, angiogenesis and metastases. The principal objective of this study was to assess the prognostic significance of NF-κB and VEGF expression in gastric cancer Methods: The tumor tissues of 154 patients with gastric cancer, all of whom underwent potentially curative resection, were immunohistochemically evaluated using monoclonal antibodies against NF-κB and VEGF. Results: Positivity rates of NF-κB and VEGF were 44.2% and 39.6%, respectively. NF-κB expression in tumor tissues was correlated significantly with VEGF expression (p < 0.001). VEGF expression was related to Lauren’s classification (p = 0.002), differentiation (p = 0.043), depth of invasion (p = 0.005), carcinoembryonic antigen (p = 0.032), and stage (p = 0.026). However, NF-κB expression was not related to any of these parameters. Univariate analysis demonstrated that NF-κB expression was significantly related with both 5-year disease free survival (65.2% vs. 46.4%, p = 0.007), and 5-year overall survival (60.0% vs. 42.5%, p = 0.014). Multivariate analysis verified that NF-κB was independently associated with disease free survival (hazard ratio: 2.082, p = 0.005), and overall survival (hazard ratio: 1.841, p = 0.008). However, VEGF did not appear to be related to adverse clinical outcome. Conclusions: NF-κB expression in tumor tissue is associated with poor survival in gastric cancer patients.