A new concept is described for methane and hydrogen storage materials involving the incorporation of magnesium-decorated fullerenes within metal-organic frameworks (MOFs). The system is modeled using a novel approach underpinned by surface potential energies developed from Lennard-Jones parameters. Impregnation of MOF pores with magnesium-decorated Mg(10)C(60) fullerenes, denoted as Mg-C(60)@MOF, places exposed metal sites with high heats of gas adsorption into intimate contact with large surface area MOF structures. Perhaps surprisingly, given the void space occupied by C(60), this impregnation delivers remarkable gas uptake, according to our modeling, which predicts exceptional performance for the Mg-C(60)@MOF family of materials. These predictions include a volumetric methane uptake of 265 v/v, the highest reported value for any material, which significantly exceeds the U.S. Department of Energy target of 180 v/v. We also predict a very high hydrogen adsorption enthalpy of 11 kJ mol(-1) with relatively little decrease as a function of H(2) filling. This value is close to the calculated optimum value of 15.1 kJ mol(-1) and is achieved concurrently with saturation hydrogen uptake in large amounts at pressures under 10 atm.