We investigated the reinforcing effect of supersaturated Al-C phases on the mechanical properties of Al/C60 composites produced via powder metallurgy followed by thermal treatment. We controlled the fractions of C60-fullerenes, nano-scale carbides, and Al-C supersaturated phases in the Al/C60 composites by adjusting the heat-treatment temperature and duration. Furthermore, we examined the contribution of each phase on the elastic and plastic behavior of the composites using scanning acoustic microscopy (SAM) and hardness measurements. After heat treatment, a supersaturated Al-C phase and an Al carbide were formed in the Al/C composites by decomposition of individually dispersed C60. This led to enhancement of the hardness and elastic modulus of the Al/C composites heat-treated at 450 and 500 °C, while these properties were reduced in the 650 °C heat-treated composite. Notably, the 500 °C heat-treated composites showed significantly high hardness and elastic modulus (approximately 250 Hv and 77.8 GPa, respectively) owing to the substantially large contribution of the supersaturated Al-C phases, which was theoretically calculated to be 851 GPa/vol% and 227 GPa/vol%, respectively. This is possibly because the well-dispersed C in the atomic scale changed the elastic bonding characteristics of the metallic bonds between the Al atoms.