Many eukaryotic cells, including animal cells and unicellular amoebae, use dynamic-actin networks to crawl across solid surfaces. Recent discoveries of actin-dependent crawling in additional lineages have sparked interest in understanding how and when this type of motility evolved. Tracing the evolution of cell crawling requires understanding the molecular mechanisms underlying motility. Here we outline what is known about the diversity and evolution of the molecular mechanisms that drive cell motility, with a focus on actin-dependent crawling. Classic studies and recent work have revealed a surprising number of distinct mechanical modes of actin-dependent crawling used by different cell types and species to navigate different environments. The overlap in actin network regulators driving multiple types of actin-dependent crawling, along with cortical-actin networks that support the plasma membrane in these cells, suggest that actin motility and cortical actin networks might have a common evolutionary origin. The rapid development of additional evolutionarily diverse model systems, advanced imaging technologies, and CRISPR-based genetic tools, is opening the door to testing these and other new ideas about the evolution of actin-dependent cell crawling.