Possible mechanisms of metal matrix strengthening caused by carbon nanostructures additions are considered. The experimental and calculated data have been compared. It is shown that the strengthening of the composite mainly resulted from the metal matrix grain refinement. The results are well consistent with Hall-Petch ratio as for copper-based composites so for aluminum-based ones if there is no carbide phase formed. When Al4C3 carbide phase formed the strengthening is caused by the new phase formation.