Considerable efforts to make palladium and palladium alloys active catalysts and a possible replacement for platinum have had a marginal success. Here we report on a structurally ordered Au10Pd₄₀Co₅₀ catalyst that exhibits comparable activity to conventional platinum catalysts in both acid and alkaline media. Electron microscopic techniques demonstrate that, at elevated temperatures, palladium cobalt nanoparticles undergo an atomic structural transition from core-shell to a rare intermetallic ordered structure with twin boundaries forming stable {111}, {110} and {100} facets via addition of gold atoms. The superior stability of this catalyst compared with platinum after 10,000 potential cycles in alkaline media is attributed to the atomic structural order of PdCo nanoparticles along with protective effect of clusters of gold atoms on the surface. This strategy of making ordered palladium intermetallic alloy nanoparticles can be used in diverse heterogeneous catalysis where particle size and structural stability matter.