The progressive oxygenation of the Earth's atmosphere was pivotal to the evolution of life, but the puzzle of when and how atmospheric oxygen (O2) first approached modern levels (∼21%) remains unresolved. Redox proxy data indicate the deep oceans were oxygenated during 435-392 Ma, and the appearance of fossil charcoal indicates O2 >15-17% by 420-400 Ma. However, existing models have failed to predict oxygenation at this time. Here we show that the earliest plants, which colonized the land surface from ∼470 Ma onward, were responsible for this mid-Paleozoic oxygenation event, through greatly increasing global organic carbon burial-the net long-term source of O2 We use a trait-based ecophysiological model to predict that cryptogamic vegetation cover could have achieved ∼30% of today's global terrestrial net primary productivity by ∼445 Ma. Data from modern bryophytes suggests this plentiful early plant material had a much higher molar C:P ratio (∼2,000) than marine biomass (∼100), such that a given weathering flux of phosphorus could support more organic carbon burial. Furthermore, recent experiments suggest that early plants selectively increased the flux of phosphorus (relative to alkalinity) weathered from rocks. Combining these effects in a model of long-term biogeochemical cycling, we reproduce a sustained +2‰ increase in the carbonate carbon isotope (δ(13)C) record by ∼445 Ma, and predict a corresponding rise in O2 to present levels by 420-400 Ma, consistent with geochemical data. This oxygen rise represents a permanent shift in regulatory regime to one where fire-mediated negative feedbacks stabilize high O2 levels.