Eukaryotic cilia and flagella are motile organelles built on a scaffold of doublet microtubules and powered by dynein ATPase motors. Some thirty years ago, two competing views were presented to explain how the complex machinery of these motile organelles had evolved. Overwhelming evidence now refutes the hypothesis that they are the modified remnants of symbiotic spirochaete-like prokaryotes, and supports the hypothesis that they arose from a simpler cytoplasmic microtubule-based intracellular transport system. However, because intermediate stages in flagellar evolution have not been found in living eukaryotes, a clear understanding of their early evolution has been elusive. Recent progress in understanding phylogenetic relationships among present day eukaryotes and in sequence analysis of flagellar proteins have begun to provide a clearer picture of the origins of doublet and triplet microtubules, flagellar dynein motors, and the 9+2 microtubule architecture common to these organelles. We summarize evidence that the last common ancestor of all eukaryotic organisms possessed a 9+2 flagellum that was used for gliding motility along surfaces, beating motility to generate fluid flow, and localized distribution of sensory receptors, and trace possible earlier stages in the evolution of these characteristics.