Mn₃O₄@CoMn₂O₄ nanoparticles (NPs) were produced at low temperature and ambient atmosphere using a one-pot two-step synthesis protocol involving the cation exchange of Mn by Co in preformed Mn₃O₄ NPs. Selecting the proper cobalt precursor, the nucleation of CoₓOy crystallites at the Mn₃O₄@CoMn₂O₄ surface could be simultaneously promoted to form Mn₃O₄@CoMn₂O₄-CoₓOy NPs. Such heterostructured NPs were investigated for oxygen reduction and evolution reactions (ORR, OER) in alkaline solution. Mn₃O₄@CoMn₂O₄-CoₓOy NPs with [Co]/[Mn] = 1 showed low overpotentials of 0.31 V at −3 mA·cm-2 and a small Tafel slope of 52 mV·dec-1 for ORR, and overpotentials of 0.31 V at 10 mA·cm-2 and a Tafel slope of 81 mV·dec-1 for OER, thus outperforming commercial Pt-, IrO2-based and previously reported transition metal oxides. This cation-exchange-based synthesis protocol opens up a new approach to design novel heterostructured NPs as efficient nonprecious metal bifunctional oxygen catalysts.