Motility often plays a decisive role in the survival of species. Five systems of motility have been studied in depth: those propelled by bacterial flagella, eukaryotic actin polymerization and the eukaryotic motor proteins myosin, kinesin and dynein. However, many organisms exhibit surprisingly diverse motilities, and advances in genomics, molecular biology and imaging have showed that those motilities have inherently independent mechanisms. This makes defining the breadth of motility nontrivial, because novel motilities may be driven by unknown mechanisms. Here, we classify the known motilities based on the unique classes of movement-producing protein architectures. Based on this criterion, the current total of independent motility systems stands at 18 types. In this perspective, we discuss these modes of motility relative to the latest phylogenetic Tree of Life and propose a history of motility. During the ~4 billion years since the emergence of life, motility arose in Bacteria with flagella and pili, and in Archaea with archaella. Newer modes of motility became possible in Eukarya with changes to the cell envelope. Presence or absence of a peptidoglycan layer, the acquisition of robust membrane dynamics, the enlargement of cells and environmental opportunities likely provided the context for the (co)evolution of novel types of motility.