Microtubules in cells consist of functionally diverse subpopulations carrying distinct post-translational modifications (PTMs). Akin to the histone code, the tubulin code regulates a myriad of microtubule functions, ranging from intracellular transport to chromosome segregation. However, how individual PTMs only occur on subsets of microtubules to contribute to microtubule specialization is not well understood. In particular, microtubule detyrosination, the removal of the C-terminal tyrosine on α-tubulin subunits, marks the stable population of microtubules and modifies how microtubules interact with other microtubule-associated proteins to regulate a wide range of cellular processes. Previously, we found that in certain cell types, only ∼30% of microtubules are highly enriched with the detyrosination mark and that detyrosination spans most of the length of a microtubule, often adjacent to a completely tyrosinated microtubule. How the activity of a cytosolic detyrosinase, vasohibin (VASH), leads to only a small subpopulation of highly detyrosinated microtubules is unclear. Here, using quantitative super-resolution microscopy, we visualized nascent microtubule detyrosination events in cells consisting of 1-3 detyrosinated α-tubulin subunits after nocodazole washout. Microtubule detyrosination accumulates slowly and in a dispersed pattern across the microtubule length. By visualizing single molecules of VASH in live cells, we found that VASH engages with microtubules stochastically on a short timescale, suggesting limited removal of tyrosine per interaction, consistent with the super-resolution results. Combining these quantitative imaging results with simulations incorporating parameters from our experiments, we provide evidence for a stochastic model for cells to establish a subset of detyrosinated microtubules via a detyrosination-stabilization feedback mechanism.