Centrosomes and cilia are microtubule-based superstructures vital for cell division, signaling, and motility. The once thought hollow lumen of their microtubule core structures was recently found to hold a rich meshwork of microtubule inner proteins (MIPs). To address outstanding questions on how distinct MIPs evolved to recognize microtubule inner surfaces, we applied computational sequence analyses, structure predictions, and experimental validation to uncover evolutionarily conserved microtubule- and MIP-binding domains named NWE, PYG, SNYG, ELLEn, and GFG-repeat by their signature motifs. These novel domains intermix with MT-binding DM10-modules and Mn-repeats in 24 Chlamydomonas and 33 human proteins. The domains specialties provided keys to identify elusive cross-species homologs, 11 hitherto unknown human MIP candidates, and functional properties for five protein subfamilies, including the microtubule seam-binding NWE and ELLEn families. Our work demonstrates that MIPs co-evolved with centrosomes and cilia, defines structural innovations that underpin centriole and axoneme assembly, and explain causes of ciliopathies.