The poor durability of Pt-based nanoparticles dispersed on carbon black is the challenge for the application of long-life polymer electrolyte fuel cells. Recent work suggests that Fe- and N-codoped carbon (Fe-N-C) might be a better support than conventional high-surface-area carbon. In this work, we find that the electrochemical surface area retention of Pt/Fe-N-C is much better than that of commercial Pt/C during potential cycling in both acidic and basic media. In situ inductively coupled plasma mass spectrometry studies indicate that the Pt dissolution rate of Pt/Fe-N-C is 3 times smaller than that of Pt/C during cycling. Density functional theory calculations further illustrate that the Fe-N-C substrate can provide strong and stable support to the Pt nanoparticles and alleviate the oxide formation by adjusting the electronic structure. The strong metal-substrate interaction, together with a lower metal dissolution rate and highly stable support, may be the reason for the significantly enhanced stability of Pt/Fe-N-C. This finding highlights the importance of carbon support selection to achieve a more durable Pt-based electrocatalyst for fuel cells.