Abstract Background The transcription factor nuclear factor-κB (NF-κB) has been implicated in gastric cancer metastasis, but the underlying molecular mechanisms remain unclear. We investigated the role of the interaction between NF-κB and signal transducers and activators of transcription 3 (STAT3) in controlling metastatic potential of gastric cancer cells. Methods Immunohistochemistry for NF-κB p65 (RelA), phospho-Tyr705-STAT3 (pSTAT3), or matrix metalloproteinase 9 (MMP9) was performed on tissue array slides containing 255 gastric carcinoma specimens. NF-κB inhibition in SNU-638 and MKN1 gastric cancer cell lines were performed by transduction with a retroviral vector containing NF-κB repressor mutant of IκBα, and STAT3 was silenced by RNA interference. We also did luciferase reporter assay, double immunofluorescence staining and immunoblotting. Cell migration and invasion were determined by wound-healing assay and invasion assay, respectively. Results NF-κB and STAT3 were constitutively activated and were positively correlated (P = 0.038) in gastric cancer tissue specimens. In cell culture experiments, NF-κB inhibition reduced STAT3 expression and activation, whereas STAT3 silencing did not affect NF-κB activation. Moreover, both NF-κB inhibition and STAT3 silencing decreased gastric cancer cell migration and invasion in a synergistic manner. In addition, both NF-κB activation and STAT3 activation were positively correlated with MMP9 in gastric cancer tissues (P = 0.001 and P = 0.022, respectively), decreased E-cadherin expression and increased Snail and MMP9 expressions in cultured cells. Conclusion NF-κB and STAT3 are positively associated and synergistically contribute to the metastatic potential of gastric cancer cells. Thus, dual use of NF-κB and STAT3 inhibitors may enhance the efficacy of the anti-metastatic treatment of gastric cancer.