The nanoscale structural, compositional, and magnetic properties are examined for annealed MnAu nanoclusters. The MnAu clusters order into the L1(0) structure, and monotonic size-dependences develop for the composition and lattice parameters, which are well reproduced by our density functional theory calculations. Simultaneously, Mn diffusion forms 5 Å nanoshells on larger clusters inducing significant magnetization in an otherwise antiferromagnetic system. The differing atomic mobilities yield new cluster nanostructures that can be employed generally to create novel physical properties.