Echoing the repeated convergent evolution of flight and vision in large eukaryotes, propulsive swimming motility has evolved independently in microbes in each of the three domains of life. Filamentous appendages—archaella in Archaea, flagella in Bacteria, and cilia in Eukaryotes—wave, whip, or rotate to propel microbes, overcoming diffusion and enabling colonization of new environments. The implementations of the three propulsive nanomachines are distinct, however: archaella and flagella rotate, while cilia beat or wave; flagella and cilia assemble at their tips, while archaella assemble at their base; archaella and cilia use ATP for motility, while flagella use ion-motive force. These underlying differences reflect the tinkering required to evolve a propulsive molecular machine, in which pre-existing machines in the appropriate contexts were iteratively co-opted for new functions, and whose origins are reflected in the resultant mechanisms. Contemporary homologies suggest that archaella evolved from a non-rotary pilus, flagella from a non-rotary appendage or secretion system, and cilia from a passive sensory structure. Here we review the structure, assembly, mechanism, and homologies of the three distinct solutions as a foundation to better understand how propulsive nanomachines evolved three times independently and to highlight principles of molecular evolution.