Cell migration is a process crucial for a variety of biological events, such as morphogenesis and wound healing. Several reports have described the possible regulation of cell migration by autophagy; however, this remains controversial. We here demonstrate that mouse embryonic fibroblasts (MEFs) lacking autophagy protein 5 (Atg5), an essential molecule of autophagy, moved faster than wild-type (WT) MEFs. Similar results were obtained for MEFs lacking Atg7 and unc-51-like kinase 1 (Ulk1), which are molecules required for autophagy. This phenotype was also observed in Atg7-deficient macrophages. WT MEFs moved by mesenchymal-type migration, whereas Atg5 knockout (KO) MEFs moved by amoeba-like migration. This difference was thought to be mediated by the level of RhoA activity, because Atg5 KO MEFs had higher RhoA activity, and treatment with a RhoA inhibitor altered Atg5 KO MEF migration from the amoeba type to the mesenchymal type. Autophagic regulation of RhoA activity was dependent on GEF-H1, a member of the RhoA family of guanine nucleotide exchange factors. In WT MEFs, GEF-H1 directly bound to p62 and was degraded by autophagy, resulting in low RhoA activity. In contrast, the loss of autophagy increased GEF-H1 levels and thereby activated RhoA, which caused cells to move by amoeba-like migration. This amoeba-like migration was cancelled by the silencing of GEF-H1. These results indicate that autophagy plays a role in the regulation of migration by degrading GEF-H1.