The nanocrystalline Mg-based metal hydrides offer a breakthrough in prospects for practical applications. In this work, we study experimentally the structure, electrochemical properties and surface segregation effect of nanocrystalline and microcrystalline Mg2M alloys and Mg2M/M’ (M=Cu, Ni; M’=C, Ni, Pd) nanocomposites. These materials were prepared by mechanical alloying (MA). In the nanocrystalline Mg2Cu powder, discharge capacity up to 30 mA h g-1 was measured. It was found that nickel substituting copper in Mg2Cu1-xNix alloy greatly improved the discharge capacity of studied material. In nanocrystalline Mg2Ni powder, discharge capacities up to 100 mA h g-1 were measured. Additionally, it was found that mechanically coated Mg-based alloys with graphite, nickel or palladium have effectively reduced the degradation rate of the studied electrode materials. Finally, the properties of nanocrystalline alloys and their nanocomposites are compared to that of microcrystalline samples. X-ray photoelectron spectroscopy studies showed that the surface segregation of Mg atoms and valence band width in the nanocrystalline Mg2M alloy are greater compared to those observed in microcrystalline Mg2M. Especially, a strong surface segregation of Mg atoms was observed for the Mg2Ni/M’ composites. In that case, Mg atoms strongly segregate to the surface and form a Mg based oxide layer under atmospheric conditions. The lower lying Ni and M’ atoms form a metallic subsurface layer and could be responsible for the observed relatively high hydrogenation rate. Furthermore, the valence band broadening observed in the nanocrystalline Mg2Ni alloys and Mg2Ni/M’ composites could also significantly influence their hydrogenation properties.