During wound healing, angiogenesis, and tumor invasion, cells often change their expression profiles of fibronectin-binding integrins. Here, we show that beta1 integrins promote random migration, whereas beta3 integrins promote persistent migration in the same epithelial cell background. Adhesion to fibronectin by alpha(v)beta3 supports extensive actin cytoskeletal reorganization through the actin-severing protein cofilin, resulting in a single broad lamellipod with static cell-matrix adhesions at the leading edge. Adhesion by alpha5beta1 instead leads to the phosphorylation/inactivation of cofilin, and these cells fail to polarize their cytoskeleton but extend thin protrusions containing highly dynamic cell-matrix adhesions in multiple directions. The activity of the small GTPase RhoA is particularly high in cells adhering by alpha5beta1, and inhibition of Rho signaling causes a switch from a beta1- to a beta3-associated mode of migration, whereas increased Rho activity has the opposite effect. Thus, alterations in integrin expression profiles allow cells to modulate several critical aspects of the motile machinery through Rho GTPases.