Perovskite oxides have attracted significant attention as energy conversion materials for metal-air battery and solid-oxide fuel-cell electrodes owing to their unique physical and electronic properties. Amongst these unique properties is the structural stability of the cation array in perovskites that can accommodate mobile oxygen ions under electrical polarization. Despite oxygen ion mobility and vacancies having been shown to play an important role in catalysis, their role in charge storage has yet to be explored. Herein we investigate the mechanism of oxygen-vacancy-mediated redox pseudocapacitance for a nanostructured lanthanum-based perovskite, LaMnO3. This is the first example of anion-based intercalation pseudocapacitance as well as the first time oxygen intercalation has been exploited for fast energy storage. Whereas previous pseudocapacitor and rechargeable battery charge storage studies have focused on cation intercalation, the anion-based mechanism presented here offers a new paradigm for electrochemical energy storage.