The compositional stability of bimetallic nanoparticles (NPs) is crucial for many applications. We have studied the coarsening of amorphous carbon supported Au-Pd NPs during annealing at 873K. Using scanning transmission electron microscopy and energy dispersive spectroscopy measurements, we show that in spite of a complete miscibility of the two metals, the particle assembly undergoes a phase separation during annealing, which leads to two distinct populations: Au-rich NPs of mean radius 3.5 nm and large Pd-rich NPs of mean radius 25 nm. Thermodynamic calculations and kinetic Monte-Carlo simulations explain this behavior which is driven by the competition between surface and mixing energy, and by the different mobilities of the two atomic species.