The evolution of flagella is of great interest to biologists because the three known varieties of flagella (eukaryotic, bacterial, and archaeal) each represent a sophisticated cellular structure that requires the interaction of many different systems.
There are two competing groups of models for the evolutionary origin of the eukaryotic flagellum (referred to as cilium below to distinguish it from its bacterial counterpart). Recent studies on the microtubule organizing center (MTOC) suggest that the most recent ancestor of all eukaryotes already had a complex flagellar apparatus.
These models argue that cilia developed from pre-existing components of the eukaryotic cytoskeleton (which has tubulin and dynein – also used for other functions) as an extension of the mitotic spindle apparatus. The connection can still be seen, first in the various early-branching single-celled eukaryotes that have a microtubule basal body, where microtubules on one end form a spindle-like cone around the nucleus, while microtubules on the other end point away from the cell and form the cilium. A further connection is that the centriole, involved in the formation of the mitotic spindle in many (but not all) eukaryotes, is homologous to the cilium, and in many cases is the basal body from which the cilium grows.
An apparent intermediate stage between spindle and cilium would be a non-swimming appendage made of microtubules with a selectable function like increasing surface area, helping the protozoan remain suspended in water, increasing the chances of bumping into bacteria to eat, or serving as a stalk attaching the cell to a solid substrate.
Regarding the origin of the individual protein components, an interesting paper on the evolution of dyneins shows that the more complex protein family of ciliary dynein has an apparent ancestor in a simpler cytoplasmic dynein (which itself has evolved from the AAA protein family that occurs widely in all archea, bacteria and eukaryotes). Long-standing suspicions that tubulin was homologous to FtsZ (based on very weak sequence similarity and some behavioral similarities) were confirmed in 1998 by the independent resolution of the 3-dimensional structures of the two proteins.