Microtubules are active biological polymers known to stochastically switch between phases of growth and shrinkage, a behavior termed ‘dynamic instability’. Microtubule treadmilling, in which the microtubule plus end grows while the minus end shrinks, is also observed in cells. While dynamic instability has been widely studied in vitro, the conditions that lead to robust microtubule treadmilling are not known. Here we investigate the mechanisms underlying microtubule treadmilling using a minimal reconstitution system with purified protein components and total-internal-reflection-fluorescence microscopy. We found that a significant fraction of microtubules polymerized from tubulin in the absence of microtubule-associated proteins (MAPs) could be classified as treadmilling, consistent with earlier reports. However, not only was the treadmilling direction of these microtubules opposite from that observed in cells, but their overall treadmilling rates were an order of magnitude smaller than measured in cells. We hypothesized that this discrepancy is due to the regulatory effects of MAPs in cellular environments. To test this hypothesis, we explored the combined effects of MAPs on microtubule assembly rates using computer simulations, constrained by published experimental observations. Our in silico experiments predicted that a combination of four MAPs (EB1, XMAP215, CLASP2 and MCAK) could promote sustained plus-end-leading treadmilling with cellular rates. Using a multi-MAP in vitro microtubule assembly assay, we tested the predictions of our computational model and found that with this minimal in vitro system, we could indeed reconstitute robust and fast plus-end-leading treadmilling, consistent with observations in cells. Our findings demonstrate that microtubule dynamics can be tuned to achieve a dynamic balance between polymerization and depolymerization at opposite polymer ends resulting in treadmilling over long periods of time.