The crystal structure of platinum-cobalt (PtCo) nanoparticles with stabilized Pt-skin layers (Pt-xAL-PtCo) has been found, for the first time, to change dramatically by conventional potential cycles between 0.05 and 1.0 V versus reversible hydrogen electrode in a N-2-saturated 0.1 M HClO4 solution at room temperature. The structure of Pt-xAL-PtCo, 3% face-centered cubic (fcc) + face-centered tetragonal (fct), was rearranged to single-phase fcc via considerable dissolution of the Co component, resulting in excellent durability while maintaining high activity for the oxygen reduction reaction at practical temperatures for fuel cells.