AbstractCentrosomes 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 the outstanding question of 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 modules named NWE, SNYG, and ELLEn, and PYG and GFG-repeat by their signature motifs. These modules intermix with MT-binding DM10-modules and Mn-repeats in 24 Chlamydomonas and 33 human proteins. The modules molecular characteristics provided keys to identify elusive cross-species homologs, hitherto unknown human MIP candidates, and functional properties for seven protein subfamilies, including the microtubule seam-binding NWE and ELLEn families. Our work defines structural innovations that underpin centriole and axoneme assembly and demonstrates that MIPs co-evolved with centrosomes and cilia.