The C-terminus of α-tubulin undergoes a detyrosination/tyrosination cycle and dysregulation of this cycle is associated with cancer and other diseases. The molecular mechanisms of tubulin tyrosination are well studied, however it has remained unknown how tyrosine is cleaved from the tubulin tail. Here, we report the crystal structure of the long-sought detyrosination enzyme, the VASH2/SVBP heterodimer at 2.2 Å resolution and the structure of the tail/VASH2/SVBP complex at 2.5 Å resolution. VASH2 possesses a non-canonical Cys-His-Ser catalytic architecture for tyrosine cleavage. The dynamics of the α1- and α2- helices of VASH2 are related to the insolubility of VASH2. SVBP plays a chaperone-like role by extensively interacting with VASH2 and stabilizing these dynamic helices. A positively charged groove around the catalytic pocket and the α1- and α2- helices of VASH2 targets the tubulin tail for detyrosination. We provide insights into the mechanisms underlying the cycle of tubulin tyrosine cleavage and religation.