Metallic nanoparticles exsolved at the surface of perovskite oxides have been recently shown to unlock superior catalytic activity and durability towards various chemical reactions of practical importance. For example, for the CO oxidation reaction, exsolved Ni nanoparticles in oxidised form exhibit site activities approaching those of noble metals. This is of particular interest for the prospect of replacing noble metals with earth-abundant metal/metal oxide catalysts in the automotive exhaust control industry. Here we show that for the CO oxidation reaction, the functionality of exsolved Ni nanoparticles can be further improved when Fe is co-exsolved with Ni, as Fe–Ni alloy nanoparticles, eventually forming mixed oxide nanoparticles. As compared to the Ni nanoparticles, the alloy nanoparticles exhibit higher site activities, greatly improved durability over 170 h of continuous testing and increased tolerance towards sulphur-based atmospheres. Similarly to the single metal nanoparticles, the alloys demonstrate outstanding microstructural stability and high tolerance towards coking. These results open additional directions for tailoring the activity and durability of exsolved materials for the CO oxidation reaction and beyond.