The detyrosination-tyrosination cycle involves the removal and religation of the C-terminal tyrosine of α-tubulin and is implicated in cognitive, cardiac, and mitotic defects. The vasohibin-small vasohibin-binding protein (SVBP) complex underlies much, but not all, detyrosination. We used haploid genetic screens to identify an unannotated protein, microtubule associated tyrosine carboxypeptidase (MATCAP), as a remaining detyrosinating enzyme. X-ray crystallography and cryo-electron microscopy structures established MATCAP's cleaving mechanism, substrate specificity, and microtubule recognition. Paradoxically, whereas abrogation of tyrosine religation is lethal in mice, codeletion of MATCAP and SVBP is not. Although viable, defective detyrosination caused microcephaly, associated with proliferative defects during neurogenesis, and abnormal behavior. Thus, MATCAP is a missing component of the detyrosination-tyrosination cycle, revealing the importance of this modification in brain formation.