The electrocatalytic performance of Pt-alloy catalysts is usually limited by the lack of long-term durability, primarily due to leaching of the non-noble element under the harsh electrochemical conditions. We find that cobalt-platinum core-shell nanostructures could sustain high catalytic activity for the oxygen reduction reaction, demonstrating 8 times of improvement in catalytic activity versus commercial Pt catalysts and no more than 13% of loss after 30,000 potential cycles. The evolutions of nanoscale and surface structures over the course of extensive potential cycling were followed by combining electron microscopic elemental mapping and electrochemical studies of CO stripping. Atomistic simulations and density functional theory calculations suggest that the core-shell nanostructure could protect the non-noble metal from leaching under the “electrochemical annealing” conditions while maintaining the beneficial mechanisms of bimetallic systems for catalytic enhancement.