Nm23-H1 has been identified as a metastasis suppressor gene, but its protein interactions have yet to be understood with any mechanistic clarity. In this study, we evaluated the proteomic spectrum of interactions made by Nm23-H1 in 4T1 murine breast cancer cells derived from tissue culture, primary mammary tumors, and pulmonary metastases. By this approach, we identified the actin-severing protein Gelsolin as binding partner for Nm23-H1, verifying their interaction by coimmunoprecipitation in 4T1 cells as well as in human MCF7, MDA-MB-231T, and MDA-MB-435 breast cancer cells. In Gelsolin-transfected cells, coexpression of Nm23-H1 abrogated the actin-severing activity of Gelsolin. Conversely, actin severing by Gelsolin was abrogated by RNA interference-mediated silencing of endogenous Nm23-H1. Tumor cell motility was negatively affected in parallel with Gelsolin activity, suggesting that Nm23-H1 binding inactivated the actin-depolymerizing function of Gelsolin to inhibit cell motility. Using indirect immunoflourescence to monitor complexes formed by Gelsolin and Nm23-H1 in living cells, we observed their colocalization in a perinuclear cytoplasmic compartment that was associated with the presence of disrupted actin stress fibers. In vivo analyses revealed that Gelsolin overexpression increased the metastasis of orthotopically implanted 4T1 or tail vein-injected MDA-MB-231T cells (P = 0.001 and 0.04, respectively), along with the proportion of mice with diffuse liver metastases, an effect ablated by coexpression of Nm23-H1. We observed no variation in proliferation among lung metastases. Our findings suggest a new actin-based mechanism that can suppress tumor metastasis.