Recent experimental data indicating axonal regeneration, axogenesis, dendritogenesis, and ciliary axoneme assembly and wellness have linked the role of cytosolic metallocarboxypeptidase 1 (CCP1/AGTPBP1/Nna1) to the microtubule network. In addition, 5 of the 6 mammalian ccp genes have been shown to participate in post-translational modifications of tubulin, which occur in the microtubules of neurons, mitotic spindles, cilia, and basal bodies. Here, we compile evidence for the idea that the occurrence of CCPs strongly correlates with the presence of cilia, suggesting that CCP functions might be primarily related to cilia and basal bodies (CBBs). In agreement with this hypothesis, CCPs were localized in centrioles, basal bodies, and mitotic spindles in HeLa cells by confocal microscopy. By reconstructing the evolutionary history of CCPs, we show their presence in the last eukaryotic common ancestor and relate each group of CCP orthologs to specific roles in CBBs. The clues presented in this study suggest that during the evolution of eukaryotes, mechanisms mediated by CCPs through tubulin post-translational modifications controlling assembly, trafficking, and signaling in the microtubules, were transferred from cilia to cell and axon microtubules.