The appearance of terrestrial land plants is thought to have accompanied an increase in atmospheric oxygen levels, producing the highest O2 concentrations estimated from the geological record, and marking the transition to a permanently oxygenated deep ocean. This Paleozoic oxygenation event, which likely peaked in the Carboniferous Period, was at least partially mediated by the development of recalcitrant, carbon-rich organic compounds in terrestrial plants. A number of studies have argued that shifts in coal formation and paleogeography led to declining preservation of these compounds on land, depressing oxygen levels in the terminal Paleozoic and early Mesozoic. In contrast, we propose that the evolution and diversification of terrestrial herbivores may have limited transport and long-term burial of terrestrial organic compounds in marine sediments, resulting in less organic carbon burial and attendant declines in atmospheric oxygen. This mechanism suggests that interactions among a triad of biological processes—marine photosynthesis, land plant colonization, and the advent of herbivory—may have dictated the long-term redox state of Earth’s surface environments over the Phanerozoic Eon.