•Al7075–graphite composites were fabricated by mechanical alloying and hot extrusion.•Mechanical properties are enhanced as function of graphite content and milling time.•The strengthening is due to grain refining, Al4C3 and increased dislocation density. The modification on the microstructure and mechanical response of some Al7075–graphite composites fabricated by mechanical alloying and hot extrusion were studied as a direct function of milling time (0–10h) and graphite concentration (0–1.5wt.%). The experimental results show that the mechanical properties of the resulting composites are enhanced by increasing both the milling time and the graphite content. This effect is attributed mainly to grain size refining, Al4C3 phase formation and an increase of the dislocation density. The yield strength of the hot-extruded samples varies with grain size according to the Hall–Petch relationship. During the hot-extrusion process, recrystallization of samples milled for 10h occurs faster than in samples with 5h of milling, which is associated to the increase of stored energy in the composites caused by the milling process.