Using density functional theory (DFT) calculations, we identify the thermodynamically stable configurations of Pt-Co alloy nanoparticles of varying Co compositions and particle sizes. Our results indicate that the most thermodynamically stable structure is a shell-by-shell configuration where the Pt atom only shell and the Co only shell alternately stack and the outermost shell consists of a Pt skin layer. DFT calculations show that the structure has substantially higher dissolution potential of the outermost Pt shell compared with pure Pt nanoparticles of approximately the same size. Furthermore, our DFT calculations also propose that the shell-by-shell structure shows much better oxygen reduction reaction (ORR) activity than conventional bulk or nanoparticles of pure Pt. These novel catalyst properties can be changed when the surfaces are adsorbed with oxygen atoms via selective segregation followed by the electrochemical dissolution of the alloyed Co atoms. However, these phenomena are thermodynamically not plausible if the chemical potentials of oxygen are controlled below a certain level. Therefore, we propose that the shell-by-shell structures are promising candidates for highly functional catalysts in fuel cell applications.