Rho signaling is increasingly recognized to contribute to invasion and metastasis. In this study, we discovered that metastasis-associated protein S100A4 interacts with the Rho-binding domain (RBD) of Rhotekin, thus connecting S100A4 to the Rho pathway. Glutathione S-transferase pull-down and immunoprecipitation assays demonstrated that S100A4 specifically and directly binds to Rhotekin RBD, but not the other Rho effector RBDs. S100A4 binding to Rhotekin is calcium-dependent and uses residues distinct from those bound by active Rho. Interestingly, we found that S100A4 and Rhotekin can form a complex with active RhoA. Using RNA interference, we determined that suppression of both S100A4 and Rhotekin leads to loss of Rho-dependent membrane ruffling in response to epidermal growth factor, an increase in contractile F-actin 'stress' fibers and blocks invasive growth in three-dimensional culture. Accordingly, our data suggest that interaction of S100A4 and Rhotekin permits S100A4 to complex with RhoA and switch Rho function from stress fiber formation to membrane ruffling to confer an invasive phenotype.