While the formation of actin-based pseudopodia is presumably an ancestral eukaryotic feature, microtubule-based pseudopodia represent later modifications that were acquired independently in different lineages. Mapping morphological information onto molecular phylogenetic trees led to different scenarios of the microtubule-based outgrowths evolution. The recent advance in the field of genomic and cell biology allows for tracking particular modifications in cytoskeletal and regulatory genes. At the same time, the picture is still dramatically incomplete, due to non-sufficient morphological data for many groups and the paucity or lack of molecular markers for robust phylogenetic reconstructions, where true eukaryotic diversity is still considerably undersampled. The obvious obstacle is also a lack of consistency and exactness in the definitions of many terms, some of which are discussed here. The importance of studying microtubule-based outgrowths function, morphology and evolution comes from the fact that they are also represented by medically relevant structures, e.g. axons, dendrites and tumor cells microtentacles. Here we review the diversity, distribution and hypothetical evolutionary origin of microtubule-based cell outgrowths in eukaryotes with an emphasis on complex surveys, where the information on the cell structure and function is taken into account along with up-to-date phylogenomic reconstructions of the phylogenetic relationships.