Palladium-nickel (PdNi) hollow nanoparticles were synthesized via a modified galvanic replacement method using Ni nanoparticles as sacrificial templates in an aqueous medium. X-ray diffraction and transmission electron microscopy show that the as-synthesized nanoparticles are alloyed nanostructures and have hollow interiors with an average particle size of 30 nm and shell thickness of 5 nm. Compared with the commercially available Pt/C or Pd/C catalysts, the synthesized PdNi/C has superior electrocatalytic performance towards the oxygen reduction reaction, which makes it a promising electrocatalyst for alkaline anion exchange membrane fuel cells and alkali-based air-batteries. The electrocatalyst is finally examined in a H2/O2 alkaline anion exchange membrane fuel cell; the results show that such electrocatalysts could work in a real fuel cell application as a more efficient catalyst than state-of-the-art commercially available Pt/C.