Herein, we describe the synthesis of Mg2FeH6 by hydrogenation of a 2.1 Mg:Fe (mol/mol) powder mixture prepared by cold roll milling (CRM) in air. The thickness of Fe layers and the amount and distribution of oxygen with number of CRM passes were systematically analyzed. CRM-induced microstructural changes were shown to play an important role in Mg2FeH6 formation. Although repeated CRM effectively decreased the Fe layer thickness to values sufficient for the fast formation of Mg2FeH6, too much CRM passes decreased the total degree of hydrogenation due to inevitable oxidation of Mg in air. Both microstructure refinement and minimal oxidation are the prerequisites for efficient Mg2FeH6 synthesis, with the former condition being achievable by optimizing the number of milling passes, and the latter one requiring CRM under an inert atmosphere.